[백준 4485번] 녹색 옷 입은 애가 젤다지?

4485번: 녹색 옷 입은 애가 젤다지?

문제 이해하기

동굴의 각 칸에는 도둑루피가 있다.

• 도둑루피가 있는 칸을 지나면, 해당 도둑루피의 크기만큼 소지금을 잃게 된다.
  • 즉, 비용이 든다는 것으로 생각하면 될 듯 하다.
  • 따라서, 최소비용으로 출구 까지 가는 것으로 생각 할 수 있다.
• 이동 가능 범위 : 상,하,좌,우 인접한 곳으로 한 칸씩 이동 가능하다.

시작점 (0,0) 도착점(n-1,n-1)

문제의 N의 크기는 125 이하다.

• 각 칸에서 이동가능한 경로는 상,하,좌,우 로 4가지 방향이 있다고 하더라도 125 125 4 = 63000 에 불과하다.
  • 거기에 log(125*125) 를 곱해도 int 형에서 커버가 된다.
• 각 테스트 케이스마다 N이 주어지는데, N이 0이 주어지면 전체 입력이 종료된다.

문제 풀이하기

• 이 문제의 각 엣지의 비용은 0 이상의 정수다 → 다익스트라로 풀이가 가능하다
• 다익스트라로 풀이시 비용은 O(ElogN) 이다
  • 이 결과는 정수를 넘지 않는다.
• Java에서 우선순위 힙은 디폴트가 min heap 이죠.

틀렸습니다의 원인

.... PQ 에 넣던 시점의 cost 가 아닌, 동적으로 계속 변하고 있는 cost 테이블의 값을 사용해, PQ에서 compare을 하도록 하고 있었다.

• pq에다가 int[3]이 아닌 int2 를 넣으려고 했어서 발생한 문제였다

public class Main {
	public static int n;
	public static int[][] board; // 보드의 각 칸은 -> 각칸의 도둑루피
	public static int[][] cost; // 각 칸까지의  최소 비용
	public static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			return o1[2] - o2[2];
		}
	});
	public static int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;

	public static void setUp() throws IOException {
		int count = 1;
		while (true) {
			String temp = br.readLine();
			if (temp.equals("0"))
				return;
			n = Integer.parseInt(temp);
			board = new int[n][n];
			cost = new int[n][n];

			// init board
			for (int r = 0; r < n; r++) {
				st = new StringTokenizer(br.readLine());
				for (int c = 0; c < n; c++) {
					board[r][c] = Integer.parseInt(st.nextToken());
				}
			}

			// init cost
			IntStream.range(0, n)
				.forEach(i -> Arrays.fill(cost[i], Integer.MAX_VALUE));
			cost[0][0] = board[0][0];

			System.out.println("Problem "+count++ +": "+solve());
		}

	}

	public static int solve() {
		pq.clear();
		pq.add(new int[] {0, 0, cost[0][0]});

		while (!pq.isEmpty()) {
			// 현재 까지에서 최소 거리인 노드를 추출한다
			int[] cur = pq.poll();
			int curCost = cost(cur[0], cur[1]);
			// 도착점에 도달하면 바로 리턴
			if (cur[0] == n - 1 && cur[1] == n - 1)
				return curCost;

			// 인접 노드
			for (int d = 0; d < dirs.length; d++) {
				int nr = cur[0] + dirs[d][0];
				int nc = cur[1] + dirs[d][1];
				if (nr < 0 || nc < 0 || nr >= n || nc >= n)
					continue;
				int nCost = curCost + board[nr][nc];
				if (cost[nr][nc] > nCost) {
					pq.add(new int[] {nr, nc, nCost});
					cost[nr][nc] = nCost;
				}
			}
		}
		return cost(n - 1, n - 1);
	}

	public static int cost(int r, int c) {
		return cost[r][c];
	}

	public static void main(String[] args) throws IOException {
		setUp();
	}
}