아이디어

• 격자에서의 다익스트라
  • $O(E \lg V)$의 우선순위 큐 다익스트라 알고리즘을 사용하였다.
• 정점 번호가 2차원으로 나타난다.
  • dist 배열(시작점에서 해당 정점까지의 최단거리)도 2차원이 된다.
• 인접한 정점 번호는 4방향에 인접한 좌표와 같다.
• 시작 정점으로부터 자신까지의 최단거리를 0이 아닌 시작 타일의 값으로 둔다.
• 간선의 가중치는 가고자 하는 타일에 적힌 값이다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int t, N;
	static int[][] map;
	static PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.w, n2.w));
	static int[][] dist;	// 0 0 -> y x
	
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	
	static int INF = Integer.MAX_VALUE / 2;
	
	public static void main(String[] args) throws Exception {
		while (true) {
			t++;
			N = Integer.parseInt(rd.readLine());
			if (N == 0) break;
			
			map = new int[N][N];
			for (int y=0; y<N; y++) {
				tk = new StringTokenizer(rd.readLine());
				for (int x=0; x<N; x++) {
					map[y][x] = Integer.parseInt(tk.nextToken());
				}
			}

			dist = new int[N][N];
			for (int y=0; y<N; y++) {
				for (int x=0; x<N; x++) {
					dist[y][x] = INF;
				}
			}
			dist[0][0] = 0;
			
			pq.offer(new Node(0, 0, 0));
			
			while (!pq.isEmpty()) {
				Node node = pq.poll();
				int y = node.y;
				int x = node.x;
				int w = node.w;

				if (dist[y][x] < w) continue;
				
				for (int d=0; d<4; d++) {
					int ny = y + dy[d];
					int nx = x + dx[d];
					if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
					
					if (w + map[y][x] < dist[ny][nx]) {
						dist[ny][nx] = w + map[y][x];
						pq.offer(new Node(ny, nx, dist[ny][nx]));
					}
				}
			}
			sb.append("Problem ").append(t).append(": ").append(dist[N-1][N-1] + map[N-1][N-1]).append('\n');
		}
		System.out.println(sb);
	}
	
	static class Node {
		int y, x, w;
		Node(int y, int x, int w) {
			this.y = y;
			this.x = x;
			this.w = w;
		}
	}
}

메모리 및 시간

• 메모리: 18656 KB
• 시간: 224 ms

리뷰

• 다익스트라 구현 방법이 가물가물해지기 시작했다. 열심히 복습하자.