[SWEA] [자바] 1949. 등산로 조성

문제 출처
swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

---

1. 풀이 접근

  ㆍ 가장 높은 봉우리를 리스트에 저장
  ㆍ 모든 지도의 위치에서 1부터 K까지 등산로를 깎음
  ㆍ 저장해둔 가장 높은 봉우리에서 출발해서 가장 낮은곳 까지 이동하는 거리를 BFS로 체크
  ㆍ 가장 멀리 이동한 거리를 저장하고 최대값 산출을 위해 비교 후 출력

---

2. 소스코드

github.com/Choi-JinYeong/Solve_Alg/tree/master/Solve_Algs_SWEA/src/SWEA_1949

Choi-JinYeong/Solve_Alg

package SWEA_1949;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class po {
	int x;
	int y;
	int n;

	public po(int x, int y, int n) {
		this.x = x;
		this.y = y;

		this.n = n;
	}
}
// 35ºÐ ¼Ò¿ä

public class Solution {
	public static int map[][], cmap[][];
	public static int N, K;
	public static int isVisit[][];
	public static ArrayList<Integer> answer;
	public static ArrayList<po> pos;

	public static int front, rear;
	public static po[] queue;
	public static int routeMAX;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		answer = new ArrayList<>();
	

		for (int t = 1; t <= T; t++) {
			String[] s1 = br.readLine().split(" ");
			N = Integer.parseInt(s1[0]);
			K = Integer.parseInt(s1[1]);
			pos = new ArrayList<>();
			map = new int[N + 1][N + 1];
			cmap = new int[N + 1][N + 1];
			isVisit = new int[N + 1][N + 1];
			queue = new po[(N + 1) * (N + 1) * 4 * 1000];
			routeMAX = Integer.MIN_VALUE;
			int MAX = Integer.MIN_VALUE;
			for (int i = 1; i <= N; i++) {
				String[] s2 = br.readLine().split(" ");
				for (int j = 1; j <= N; j++) {
					map[i][j] = Integer.parseInt(s2[j - 1]);
					cmap[i][j] = map[i][j];
					isVisit[i][j] = 0;
					if (MAX < map[i][j])
						MAX = map[i][j];
				}
			}

			for (int i = 1; i <= N; i++) {

				for (int j = 1; j <= N; j++) {
					if (MAX == map[i][j]) {
						// System.out.println(j+ " / " + i);
						pos.add(new po(j, i, MAX));
					}
				}
			}

			solve();
			System.out.println("#" + t + " " + routeMAX);
		}
	}

	public static void solve() {
		for (int k = 1; k <= K; k++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					cmap[i][j] -= k;
					for (int a = 0; a < pos.size(); a++) {
						po p = pos.get(a);
						bfs(p.x, p.y);
					}
					clear();
				}
			}
		}

	}

	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };

	public static void bfs(int x, int y) {

		queue[rear++] = new po(x, y, 1);

		while (front != rear) {
			po p = queue[front++];

			routeMAX = Math.max(routeMAX, p.n);

			int px = p.x;
			int py = p.y;

			for (int i = 0; i < 4; i++) {
				int tx = px + dx[i];
				int ty = py + dy[i];
				if (isVaild(px, py) == true) {
					if (isVaild(tx, ty) == true && cmap[py][px] - cmap[ty][tx] >= 1) {
						isVisit[ty][tx] = 1;
						queue[rear++] = new po(tx, ty, p.n + 1);
					}
				}
			}

		}

	}

	public static boolean isVaild(int x, int y) {
		if (x < 1 || x > N || y < 1 || y > N)
			return false;
		else
			return true;
	}

	public static void clear() {

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				isVisit[i][j] = 0;
				cmap[i][j] = map[i][j];
			}
		}
		front = rear = 0;
	}
}

---

3. 맺음말

  ㆍ 체감난이도 : 보통
  ㆍ 지도의 크기인 N이 8까지밖에 안되서 모든 경우 탐색해도 시간안에 풀 수 있음. 등산로를 깎을 때 최대 K개 까지 깎을 수 있는 만큼 1부터 반복해서 진행한다까지만 생각이 도달하면 충분히 풀 수 있음. 풀이과정 자체는 굉장히 단순함.
  ㆍ 반복이 너무 많아 시간이 초과할 것 같은 경우 최대한 줄이기 위해 구현할 때 대략적인 시간복잡도를 고려하는 것이 좋음.
  ㆍ 더욱 좋은 풀이방법이나 보완할 수 있는 부분, 또는 문제가 될 수 있는 부분들은 알려주시면 감사하겠습니다.