[다익스트라] SWEA1249 [S/W 문제해결 응용] 4일차 - 보급로 (JAVA)

SWEA / D4

1249. 보급로

문제 정보

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

SW Expert Academy

 

문제 접근

격자에서 시작점부터 도착점까지 가는 최소 비용을 구하는 문제다. 격자 + 최단거리라는 조건만 보고 처음엔 당연히 BFS라고 생각했다. 그래서 첫 두 번의 시도를 BFS로 최단거리를 구하려고 했는데, 답이 제대로 나오지 않았다. 원인을 찾다가 BFS의 전제 조건 자체를 잘못 알고 있었다는 걸 깨닫고, 다익스트라를 새로 공부해서 다시 풀었다.

시도 기록

1~2차 시도 : 일반 BFS

Queue에 좌표를 넣고 방문 체크하면서 탐색. 최단 경로 길이는 나오지만 최소 비용이 나오지 않아 실패

3차 시도 : 다익스트라

Queue를 PriorityQueue로 바꾸고, 방문 배열 대신 누적 비용 배열(dist)로 관리해서 해결

BFS로는 왜 안 되는가

BFS가 최단거리를 보장하는 이유는 모든 간선의 가중치가 동일하다는 전제가 있기 때문이다. 가중치가 다 같으니까 먼저 큐에 들어간 노드가 무조건 더 가까운 노드이고, 그래서 한 번 방문한 칸은 다시 볼 필요가 없다.

그런데 이 문제는 칸마다 복구 시간이 0에서 9까지 다르다. 즉 간선 가중치가 서로 다른 그래프다. 이렇게 되면 먼저 도착한 경로가 더 저렴한 경로라는 보장이 사라진다. 칸 수가 적은 우회로보다, 한 칸 더 돌아가지만 숫자가 작은 길이 총합에서 더 싼 경우가 생긴다.

BFS 실패의 핵심 원인

방문 배열이 최적해를 잘라먹는다

비싼 경로가 먼저 도달해서 visited를 찍어버리면, 나중에 오는 저렴한 경로가 그 칸으로 아예 들어갈 수 없다.

FIFO 순서가 비용 순서와 다르다

일반 Queue는 들어온 순서대로 꺼낸다. 비용이 다른 그래프에서는 "먼저 들어온 것"과 "제일 싼 것"이 일치하지 않는다.

다익스트라로 바꾼 부분

다익스트라는 결국 BFS의 확장판이다. 탐색 구조는 그대로 두고 어떤 노드를 다음에 꺼낼지의 기준만 바꾸면 된다. BFS 코드에서 실제로 손댄 건 두 곳뿐이었다.

동작 원리

항상 가장 싼 노드를 먼저 확정한다

PriorityQueue에서 꺼낸 노드는 그 시점에 미확정 노드 중 가장 저렴하다. 가중치가 음수가 아니라면 더 돌아서 이 노드를 더 싸게 오는 방법은 존재하지 않는다. 그래서 꺼낸 순간 최단거리가 확정된다.

낡은 노드는 건너뛴다

같은 좌표가 갱신될 때마다 큐에 여러 번 들어간다. 꺼낸 비용이 현재 dist보다 크면 이미 더 좋은 경로로 처리된 낡은 데이터이므로 continue로 넘긴다.

코드

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

class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] board;
    static int[][] dist;
    static int n;
    
    static class Node implements Comparable<Node> {
        int x, y, cost;

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

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

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

        for (int tc = 1; tc <= t; tc++) {
            n = Integer.parseInt(br.readLine().trim());
            board = new int[n][n];

            for (int i = 0; i < n; i++) {
                String str = br.readLine().trim();
                for (int j = 0; j < n; j++) {
                    board[i][j] = str.charAt(j) - '0';
                }
            }

            dijkstra(0, 0);
            sb.append("#").append(tc).append(" ").append(dist[n - 1][n - 1]).append("\n");
        }
        System.out.print(sb);
    }

    static void dijkstra(int x, int y) {
        dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[x][y] = 0;
        pq.offer(new Node(x, y, 0));

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

            if (cur.cost > dist[cur.x][cur.y]) continue;
            if (cur.x == n - 1 && cur.y == n - 1) return;

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

                int nCost = cur.cost + board[nx][ny];
                if (nCost < dist[nx][ny]) {
                    dist[nx][ny] = nCost;
                    pq.offer(new Node(nx, ny, nCost));
                }
            }
        }
    }
}