[백준] 1261번 알고스팟 풀어보기 [Java]

(1,1)부터 (M,N)까지 가는 루트 중 최소로 벽을 부술 수 벽의 개수를 구하는 문제이다.

 

👨‍🏫 풀이

단순히 bfs로 풀면된다. 그리고 벽이 있는 경우, 벽을 부수고 가는 경우를 계산한다. 도착지까지 가는 루트 중 벽을 부술 수 있는 벽의 개수를 구하는 문제이기 때문에, Priority queue로 벽을 적게 부수는 경우가 가장 top에 올라오도록 했다.

👨🏻‍💻 코드

package 번1261;

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

public class Main {
    static int N,M;
    static int[][] map;
    static int[][] isVisited;
    static int ans = Integer.MAX_VALUE;
    static int[] mX = {0,0,1,-1};
    static int[] mY = {-1,1,0,0};
    static class Node implements Comparable<Node>{
        int x,y;
        int cnt;

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

        @Override
        public int compareTo(Node o) {
            return cnt - o.cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[M][N];
        isVisited = new int[M][N];
        for(int i = 0 ; i < M ; i++){
            Arrays.fill(isVisited[i], -1);
        }

        for(int i = 0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            String tmp = st.nextToken();
            for(int j = 0 ; j < N ; j++){
                map[i][j] = tmp.charAt(j) - '0';
            }
        }

        bfs();
        System.out.println(ans);

    }

    private static void bfs() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(0,0,0));
        isVisited[0][0] = 0;
        while(!q.isEmpty()){
            Node node = q.poll();
            int x = node.x; int y = node.y; int cnt = node.cnt;

            if(x == M - 1 && y == N - 1){
                ans = cnt;
                return;
            }
            for(int i = 0 ; i < 4 ; i++){
                int nX = mX[i] + x ; int nY = mY[i] + y;

                if(nX < 0 || nX >= M || nY < 0 || nY >= N) continue;
                if(isVisited[nX][nY] != -1) continue;

                if(map[nX][nY] == 1){ // 벽을 뚫는 경우
                    q.add(new Node(nX,nY, cnt + 1));
                    isVisited[nX][nY] = cnt + 1;
                }  else { // 벽을 뚫지 않는 경우
                    q.add(new Node(nX, nY, cnt));
                    isVisited[nX][nY] = cnt;
                }
            }
        }
    }
}