[JAVA] SWEA 1249 보급로

문제

사실상 백준 4485번 '녹색 옷 입은 애가 젤다지?' 문제와 동일하다.
https://www.acmicpc.net/problem/4485

입력

가장 첫 줄은 전체 테스트케이스의 수이다.
각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.
그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.

출력

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다.
같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.

풀이: 다익스트라

1. N*N개의 가상의 지점을 가정하고, 각 노드의 소요 시간을 지점 간 이동 거리 간선으로 두는 그래프를 생성한다.
2. 그래프에서 다익스트라 알고리즘을 적용한다.

코드

package swea;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class p보급로 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		public Node(int end, int weight) {
			super();
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return weight - o.weight;
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		int testcase = Integer.parseInt(br.readLine());
		for (int t = 1; t <= testcase; t++) {
			int N = Integer.parseInt(br.readLine());
			int[][] thief = new int[N][N];
			for (int i = 0; i < N; i++) {
				String input = br.readLine();
				for (int j = 0; j < N; j++) {
					thief[i][j] = input.charAt(j) - 48;
				}
			}

			int node = (int) Math.pow(N, 2) + 1;
			boolean[] visited = new boolean[node];
			ArrayList<Node>[] adj = new ArrayList[node];
			for (int i = 0; i < node; i++) {
				adj[i] = new ArrayList<Node>();
			}
			adj[0].add(new Node(1, thief[0][0]));
			for (int i = 1; i < node; i++) {
				int posI = (i - 1) / N;
				int posJ = (i - 1) % N;
				if (posJ < N - 1) {
					adj[i].add(new Node(i + 1, thief[posI][posJ + 1]));
				}
				if (posJ > 0) {
					adj[i].add(new Node(i - 1, thief[posI][posJ - 1]));
				}
				if (posI < N - 1) {
					adj[i].add(new Node(i + N, thief[posI + 1][posJ]));
				}
				if (posI > 0) {
					adj[i].add(new Node(i - N, thief[posI - 1][posJ]));
				}
			}

			PriorityQueue<Node> pq = new PriorityQueue<>();
			int[] distance = new int[node];
			Arrays.fill(distance, Integer.MAX_VALUE);
			distance[0] = 0;
			pq.offer(new Node(0, 0));

			while (!pq.isEmpty()) {
				Node cur = pq.poll();
				if (visited[cur.end])
					continue;
				visited[cur.end] = true;

				for (Node n : adj[cur.end]) {
					if (distance[n.end] > distance[cur.end] + n.weight) {
						distance[n.end] = distance[cur.end] + n.weight;
						pq.offer(new Node(n.end, distance[n.end]));
					}
				}
			}
			System.out.println("#" + t + " "+distance[node-1]);
		}
	}
}