1249. 보급로

문제

[SWEA-1249] 보급로

---

문제 해결 아이디어

2차원 배열 지도의 거리를 Node 객체 좌표 별로 갱신하는게 🦵킥! 전형적인 다익스트라

조건

• 방문 거리 고려하지 않고, 오직 복구 비용 (가중치)민 고려
• 시작점과 도착점이 정해져있음

Dijkstra 접근

• Node 객체를 생성하여 x,y 좌표 와 dist 시작점 부터 누적 거리를 저장
• dist[][] 2차원 배열 Integer.MAX_VALUE로 초기화

PriorityQueue 활용

• PriorityQueue에 Node의 dist 오름차순으로 정렬 (짧은 거리)
• 방문 배열 없이, 이미 해당 좌표까지 더 짧은 거리가 저장되어 있으면 contiunue

if (dist[cur.x][cur.y] < cur.dist) continue;

• 2차원 배열 지도에 4방향으로 탐색 (범위 벗어 나면 continue)
• 현재 좌표까지의 거리(복구비용) + 다음 방향 까지 거리(복구비용)이 이미 존재하는 다음 좌표에 대한 거리(복구비용) 보다 작으면 갱신

---

코드

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

public class Solution1249 {
	static int T;
	static int N;
	static int[][] map;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int minCost;

	static class Node {
		int x;
		int y;
		int dist;

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

	static int dijkstra(Node s) {
		// 시작점 부터 거리 배열 초기화
		int dist[][] = new int[N][N];
		for (int i = 0; i < N; i++) {
			Arrays.fill(dist[i], Integer.MAX_VALUE);
		}
		dist[s.x][s.y] = s.dist;

		PriorityQueue<Node> pq = new PriorityQueue<>(
			Comparator.comparingInt((Node n) -> n.dist));

		pq.offer(s);

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

			if (dist[cur.x][cur.y] < cur.dist) continue; // 이미 더 짧은 거리 찾음

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
	
				if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

				int cost = cur.dist + map[nx][ny];
				if (dist[nx][ny] > cost) {
					dist[nx][ny] = cost;
					pq.offer(new Node(nx, ny, cost));
				}
			}
		}
		return dist[N-1][N-1];
	}
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = str.charAt(j) - '0';
				}
			}
			
			minCost = dijkstra(new Node(0, 0, 0));
			System.out.printf("#%d %d\n", tc, minCost);
		}
	}
}