bj2665-미로만들기(다익스트라)

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

 

이 문제와 같이 2차원 배열에서 다익스트라를 쓰는 문제는 처음 접해보는 문제이다.

 

dy, dx는 모두 가중치를 가진 엣지라고 생각한다.

벽으로 가는 엣지는 가중치가 있는 엣지이고,

벽이 아닌 곳으로 가는 엣지는 가중치가 없는 엣지이다.

 

그렇게 마지막 목표로의 최단거리를 찾는 문제이다.

 

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

public class Main {

    static int N;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int[][] map, dist;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        initialize();
        dijkstra();
        System.out.println(dist[N-1][N-1]);
    }

    private static void dijkstra() {
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.value - o2.value);
        queue.add(new Node(0,0, 0));
        dist[0][0] = 0;
        while(!queue.isEmpty()){
            Node temp = queue.poll();
            int temp_y = temp.y;
            int temp_x = temp.x;
            for(int i = 0; i < 4; i++){
                int next_y = temp.y + dy[i];
                int next_x = temp.x + dx[i];
                if(next_x < 0 || next_x >= N || next_y < 0 || next_y >= N)continue;
                if(dist[next_y][next_x] <= dist[temp_y][temp_x] + 1)continue;
                if(map[next_y][next_x] == 1)dist[next_y][next_x] = dist[temp_y][temp_x];
                if(map[next_y][next_x] == 0)dist[next_y][next_x] = dist[temp_y][temp_x] + 1;
                queue.add(new Node(next_y, next_x, dist[next_y][next_x]));
            }
        }
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        map = new int[N][N];
        for(int y = 0; y < N; y++){
            String line = bufferedReader.readLine();
            for(int x = 0; x < N; x++){
                map[y][x] = line.charAt(x) - '0';
            }
        }

        dist = new int[N][N];
        for(int y = 0; y < N; y++){
            for(int x = 0; x < N; x++){
                dist[y][x] = Integer.MAX_VALUE;
            }
        }
    }
}
class Node{
    int y;
    int x;
    int value;

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