[백준 1261 JAVA] 알고스팟

다익스트라 알고리즘 문제

bfs를 하며 조건이 있다면 다익스트라라고 하는 것 같다.

 

길이 상관없이 도착점에 최소의 벽을 부수고 도달하면 되는 문제이다.

따라서 우선순위 큐를 선언한 뒤, 벽을 부순 횟수별로 정렬을하여 우선순위 큐에 넣어준다.

어디든 벽을 부순 횟수만 최소이면 되니, 방문처리까지 해준다.

 

ex )

벽을 부순 횟수가 0인 노드에서 탐색 => bfs로 탐색하며 주변에 벽이 있다면, 벽부순카운트 +1 및 방문처리 후 우선순위큐에 넣어줌.

(이러면 지점이 벽을 최소로 부수는 횟수로 큐에 들어감.)

만약 0회 부순 경로가 다 소진된다면, 다음 최소인 1회부순 경로를 탐색, 위 절차반복

 

이런식으로 진행되다보니 도달점에 항상 최소치로 도달할 수 있다.

 

위의 로직으로 탐색을 하다 도착점에 도달하면 풀리는 문제이다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node{
    int x,y,count;
    public Node(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}
class Main{
    static int[] moveX = {-1,0,1,0}; // 좌,상,우,하
    static int[] moveY = {0,1,0,-1};
    static int N,M;
    static Boolean[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken()); //가로
        N = Integer.parseInt(st.nextToken()); //세로

        map = new Boolean[N][M];

        for(int i =0 ;i<N; i++){
            String line = br.readLine();
            Arrays.fill(map[i],false);
            for(int j =0; j<M; j++){
                if (line.charAt(j) =='1') map[i][j] = true;
            }
        }
        System.out.println(bfs(0,0));


    }
    public static int bfs(int x, int y){
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.count-o2.count;
            }
        });
        Boolean[][] visit = new Boolean[N][M];
        for(int i = 0 ;i<N;i++){
            Arrays.fill(visit[i],false);
        }
        pq.offer(new Node(x,y,0));
        visit[x][y] = true;
        int dx,dy;
        while(!pq.isEmpty()){
            Node node = pq.poll();
            if(node.x == M-1 && node.y == N-1){
                return node.count;
            }
            for( int i =0; i<4; i++){
                dx = node.x+moveX[i];
                dy = node.y+moveY[i];

                if(dx<0 || dy<0 || dx>=M|| dy>=N){
                    continue;
                }
                int nextCnt = node.count;
                if(!visit[dy][dx]){
                    visit[dy][dx] = true;
                    if (map[dy][dx]) nextCnt++;
                    pq.offer(new Node(dx,dy,nextCnt));
                }
            }
        }
        return 0;
    }
}