[BaekJoon] 4485번 녹색 옷 입은 애가 젤다지? (Java) 문제 풀이 [Gold 4]

문제

https://www.acmicpc.net/problem/4485

 

어떻게 풀 것인가?

문제의 내용은 참 재밌다.

 

N x N 크기의 동굴 맵에서 (0,0)에서 (N-1,N-1)까지 가는데 각 칸마다 잃는 "도둑루피" 비용이 있고, 최소로 루피를 잃으면서 오른쪽 아래까지 이동하는 경로를 찾는 문제의 핵심은 결국엔 최단경로를 알아내야 한다는 것이다.

 

격자판 이차원 배열에서의 다익스트라를 사용하는 것이 핵심이다.

 

격자판에서의 다익스트라

• (0,0)에서 (N-1,N-1)로 이동
• 각 칸을 "정점"으로 보고,
  각 이동은 "간선 비용 = 다음 칸의 도둑루피"로 간주
• 시작 지점도 루피를 잃으므로, 초기 비용이 map[0][0]

다익스트라 알고리즘 절차

1. weight[x][y]: (x,y)까지 오면서 잃은 루피의 최소값을 저장
2. 우선순위 큐(PriorityQueue): 현재까지의 비용(루피 손실)이 적은 칸을 먼저 방문
3. 상하좌우 인접 칸만 이동
4. 이미 더 좋은 경로로 방문한 칸이면 무시
   (visited 배열로 체크하거나, weight[x][y]를 갱신한 경우에만 다시 방문)

 

내 코드 

import java.io.*;
import java.util.*;

public class Main {

	private static int N;
	private static int[][] map;
	private static int[][] weight;
	private static boolean[][] visited;
	private static int[] dx = { 0, 0, -1, 1 };
	private static int[] dy = { 1, -1, 0, 0 };

	private static final int INF = 999999;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int index = 1;

		while (true) {
			N = Integer.parseInt(br.readLine());
			if (N == 0)
				break;

			map = new int[N][N];
			visited = new boolean[N][N];
			weight = new int[N][N];

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					weight[i][j] = INF;
				}
			}
			Dijkstra(0, 0, map[0][0]);

			sb.append("Problem ").append(index++).append(": ").append(weight[N - 1][N - 1]).append("\n");
		}
		System.out.println(sb);

	}

	private static void Dijkstra(int x, int y, int money) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		visited[x][y] = true;
		pq.offer(new Node(x, y, money));

		while (!pq.isEmpty()) {
			Node node = pq.poll();

			for (int i = 0; i < 4; i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];

				if (range(nx, ny) && !visited[nx][ny] && weight[nx][ny] > (map[nx][ny] + node.weight)) {
					weight[nx][ny] = map[nx][ny] + node.weight;
					visited[nx][ny] = true;
					pq.offer(new Node(nx, ny, weight[nx][ny]));
				}
			}
		}

	}

	private static boolean range(int x, int y) {
		return 0 <= x && x < N && 0 <= y && y < N;
	}

	static class Node implements Comparable<Node> {
		int x, y;
		int weight;

		public Node(int x, int y, int weight) {
			this.x = x;
			this.y = y;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node n) {
			return this.weight - n.weight;
		}

	}
}