[백준 알고리즘] 20046번: Road Reconstruction (JAVA)

https://www.acmicpc.net/problem/20046

 

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

public class Main {
    static int m, n;
    static int INF = 1000 * 1000 + 1;
    static int[][] arr;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] min_dis;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        arr = new int[m][n];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        if (arr[0][0] == -1 || arr[m-1][n-1] == -1) {
            System.out.println(-1);
            return;
        }
        int ans = dijkstra(0, 0);
        System.out.println(ans);
    }

    public static int dijkstra(int x, int y) {
        min_dis = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(min_dis[i], INF);
        }
        PriorityQueue<Pos> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
        min_dis[x][y] = (arr[x][y] == 0 ) ? 0 : arr[x][y];
        pq.offer(new Pos(x, y, min_dis[x][y]));

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

            if (cur.x == m - 1 && cur.y == n - 1) return min_dis[cur.x][cur.y];

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

            for (int i = 0; i < 4; i++) {
                int xx = cur.x + dx[i];
                int yy = cur.y + dy[i];
                if (0 <= xx && xx < m && 0 <= yy && yy < n && arr[xx][yy] != -1) {
                    int cost = arr[xx][yy]  + cur.cost;
                    if (min_dis[xx][yy] > cost) {
                        min_dis[xx][yy] = cost;
                        pq.offer(new Pos(xx, yy, cost));
                    }
                }
            }
        }
        return -1;
    }
}

class Pos {
    int x;
    int y;
    int cost;

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

 

 

풀이

• 문제를 풀면서 주의해야 할 부분은 시작점인 0,0을 무조건 0으로 초기화하면 안된다는 것입니다 ! 시작 지점이 막혀있을 수도 있으며 (-1), 시작 지점에 도로가 없는 상태(1 or 2)일 수도 있기 때문에 -1일 경우 -1을 리턴하도록, 1 or 2일 경우 해당 값을 가지고 갈 수 있도록 초기화 해줘야 합니다 ! 
• 또한 해당 문제를 최단 경로를 찾는 알고리즘인 BFS로 풀이하면 안될까라는 생각을 할 수도 있지만, BFS의 경우엔 모든 구간에서 똑같은 가중치를 가지고 있어야 하기에 위 문제와 같이 가중치가 1과 2로 다른 경우 다익스트라로 풀이하여햐 합니다 !