1249. 보급로

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

분류

그래프 탐색

힙 (우선순위 큐)

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

각 칸에 대해 비용 최솟값을 갱신해가면서 각 칸을 우선순위 큐에 넣는다.

처음에는 (1,0)과 (0,1)이 우선순위 큐에 들어갈 것이고

우선순위 큐에 있는 내용을 하나씩 꺼내가며 네 방향의 칸에 대해 우선순위 큐에 다시 넣는다.

 

우선순위 큐에서 꺼낸 게 (N-1, N-1)이라면 해당 칸의 비용이 최솟값이 된다.

 

시행착오

없음

 

코드

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

class Solution{

	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int tc = 1; tc <= T; ++tc){
			int N = Integer.parseInt(br.readLine());
			Queue<Node> pq = new PriorityQueue<Node>();
			int[][] map = new int[N][N];
			int[][] cost = new int[N][N];

			for (int i = 0; i < N; i++){
				String[] arr = br.readLine().split("");
				for (int j = 0; j < N; j++){
					map[i][j] = Integer.parseInt(arr[j]);
					cost[i][j] = Integer.MAX_VALUE;
				}
			}

			cost[0][0] = 0;

			pq.add(new Node(1, 0, map[1][0]));
			pq.add(new Node(0, 1, map[0][1]));

			int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

			while (!pq.isEmpty()){
				Node n = pq.poll();
				if (cost[n.x][n.y] <= n.cost) continue;

				cost[n.x][n.y] = n.cost;

				for (int i = 0; i < 4; i++){
					int x = n.x + dx[i], y = n.y + dy[i];

					if (x < 0 || y < 0 || x >= N || y >= N) continue;

					if (cost[x][y] > n.cost + map[x][y]) pq.add(new Node(x, y, n.cost + map[x][y]));
				}
			}

			System.out.println("#" + tc + " " + cost[N - 1][N - 1]);
		}
	}

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

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

		public int compareTo(Node n){
			if (this.cost > n.cost) return 1;
			if (this.cost < n.cost) return -1;

			return 0;
		}
	}
}