[Baekjoon Online Judge] 4485 - 녹색 옷 입은 애가 젤다지? / Java

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

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int N, testCase = 0, answer;
	static int[][] map, distance;
	static PriorityQueue<Pos> q = new PriorityQueue<>();
	static int INF = 1000000;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static class Pos implements Comparable<Pos> {
		int r;
		int c;
		int cost;

		public Pos(int r, int c, int cost) {
			this.r = r;
			this.c = c;
			this.cost = cost;
		}

		@Override
		public int compareTo(Pos o) {
			return this.cost - o.cost;
		}
	}

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

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

			if (N == 0) {
				break;
			}

			map = new int[N][N];
			distance = 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());

					distance[i][j] = INF;
				}
			}

			answer = 0;
			q.clear();
			answer = bfs();

			sb.append("Problem ").append(++testCase).append(": ").append(answer).append("\n");
		}
		System.out.println(sb);
	}

	private static int bfs() {
		q.offer(new Pos(0, 0, map[0][0]));
		distance[0][0] = map[0][0];

		int currR, currC;
		while (!q.isEmpty()) {
			Pos curr = q.poll();
			currR = curr.r;
			currC = curr.c;

			if (currR == N - 1 && currC == N - 1) {
				break;
			}

			for (int dir = 0; dir < 4; dir++) {
				int nextR = currR + dr[dir];
				int nextC = currC + dc[dir];

				// 경계 체크
				if (nextR >= 0 && nextR < N && nextC >= 0 && nextC < N) {
					// 다음 지점까지 최소거리라면 갱신
					if (distance[currR][currC] + map[nextR][nextC] < distance[nextR][nextC]) {
						distance[nextR][nextC] = distance[currR][currC] + map[nextR][nextC];
						q.offer(new Pos(nextR, nextC, distance[nextR][nextC]));
					}
				}
			}
		}
		return distance[N - 1][N - 1];
	}
}