백준 2665번 : 미로만들기 java

이 문제는 미로의 구조를 입력받은 뒤 방을 최대한 적게 바꾸고 끝 점에 도달할 때 몇 개의 방을 바꾸어야 하는지에 대한
문제입니다.

이 문제를 풀기 위해서는 큐에 정점의 좌표와 그 좌표에 도달할 때 몇 개의 방을 바꾸었는지를 저장한 후 방을 바꾼 개수를 기준으로 정점들을 오름차순으로 정렬해야 합니다.

이를 위해서 우선순위 큐를 사용하였고 큐에서 꺼낸 정점들은 bfs를 이용하여 주변의 노드들을 탐색해주었습니다.

---

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

public class Main {
    static int N;
    static int[][] map;
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};

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

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        for(int i = 0; i<N; i++){
            String[] input = br.readLine().split("");

            for(int j = 0; j<N; j++)
                map[i][j] = Integer.parseInt(input[j]);
        }

        int count = findNum();
        System.out.println(count);
    }

    static int findNum(){
        boolean[][] visited = new boolean[N][N];
        int count = 0;

        Queue<Node> q = new PriorityQueue<>();
        q.offer(new Node(0, 0, 0));
        visited[0][0] = true;

        while(!q.isEmpty()){
            Node a = q.poll();

            if(a.row == N-1 && a.col == N-1) {
                count = a.blackCount;
                break;
            }

            for(int i = 0; i<4; i++){
                int dr = a.row + dR[i];
                int dc = a.col + dC[i];

                if(dr<0||dc<0||dr>=N||dc>=N)
                    continue;
                if(visited[dr][dc])
                    continue;

                if(map[dr][dc] == 0)
                    q.offer(new Node(dr, dc, a.blackCount+1));
                else
                    q.offer(new Node(dr, dc, a.blackCount));

                visited[dr][dc] = true;
            }
        }

        return count;
    }
}
class Node implements Comparable<Node>{
    int row, col, blackCount;

    Node(int row, int col, int blackCount){
        this.row = row;
        this.col = col;
        this.blackCount = blackCount;
    }

    @Override
    public int compareTo(Node a){
        return this.blackCount - a.blackCount;
    }
}

우선순위 큐를 이용하여 정렬 기준을 바꾼 후 bfs를 적용시키면 되는 문제였습니다.