👨‍💻 문제

---

✍️ 풀이

📚 우선순위 큐

단순한 미로찾기 BFS와 비슷한 문제이다.
다른 점이라곤 최단시간을 찾는 대신 벽을 부수는 최소횟수를 구하는 것이다.

벽을 피해 최단시간을 구하는 기존의 미로찾기는 그냥 큐를 사용하면 된다.

// 시간
#0 : 0
#1 : 1 1 1 1
#2 : 1 1 1 2 2 2

무조건 짧은 시간이 앞으로 오기 때문이다.

하지만 최단횟수를 구해야 하는 해당 문제에 큐를 사용하게 되면,
벽을 부순 횟수가 높은 요소가 앞으로 오게 될 수 있다.

// 붕괴 횟수
#0 : 0
#1 : 0 1 0 0
#2 : 1 0 0 0 1 0

그렇기에 해당 문제는 우선순위 큐를 활용하여,
벽을 부순 횟수가 낮은 요소부터 탐색하도록 한다.

    private static class State implements Comparable<State>{
        int r, c;
        int breakWallCnt;

        public State(int r, int c, int breakWallCnt) {
            this.r = r;
            this.c = c;
            this.breakWallCnt = breakWallCnt;
        }

        public int compareTo(State s) {
            return breakWallCnt - s.breakWallCnt;
        }
    }
    
    private static PriorityQueue<State> pq = new PriorityQueue<>();

🎇 BFS

단순 미로 BFS와 유사하다.
단, 항상 비용을 더하지 않고, 벽일 경우만 비용을 더한다.

    private static void bfs() {
        breakWallCnts = new int[N][N];
        for (int[] arr : breakWallCnts) {
            Arrays.fill(arr, Integer.MAX_VALUE);
        }

        pq.add(new State(0, 0, 0));
        breakWallCnts[0][0] = 0;

        while (!pq.isEmpty()) {
            State state = pq.poll();

            for (int dir=0; dir<4; dir++) {
                int r = state.r + dr[dir];
                int c = state.c + dc[dir];

                if (r < 0 || r == N || c < 0 || c == N) {
                    continue;
                }

                int breakWallCnt = state.breakWallCnt + (isEmpty[r][c] ? 0 : 1);

                if (breakWallCnts[r][c] > breakWallCnt) {
                    breakWallCnts[r][c] = breakWallCnt;
                    if (r==N-1 && c==N-1) {
                        return;
                    }
                    pq.add(new State(r, c, breakWallCnt));
                }
            }
        }
    }

기본 미로 BFS와 마찬가지로 이미 방문한 곳은 방문하지 않는다.
위 코드에서는 현재 비용이 낮을 때 방문한다고 되어 있는데,

어차피 우선순위 큐를 활용하기에 더 높은 비용이 무조건 낮은 비용 이후에 들어온다.
비용을 기록하지 않고, 방문하였는가를 저장하여도 좋다.

---

📄 전체 소스코드

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

public class _2665 {

    private static class State implements Comparable<State>{
        int r, c;
        int breakWallCnt;

        public State(int r, int c, int breakWallCnt) {
            this.r = r;
            this.c = c;
            this.breakWallCnt = breakWallCnt;
        }

        public int compareTo(State s) {
            return breakWallCnt - s.breakWallCnt;
        }
    }

    private static int N;
    private static boolean[][] isEmpty;

    private static PriorityQueue<State> pq = new PriorityQueue<>();
    private static int[][] breakWallCnts;

    private static int[] dr = new int[] {-1,0,1,0};
    private static int[] dc = new int[] {0,1,0,-1};

    public static void main(String[] args) throws IOException {
        input();
        bfs();
        System.out.println(breakWallCnts[N-1][N-1]);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        isEmpty = new boolean[N][N];
        for (int r=0; r<N; r++) {
            String str = br.readLine();
            for (int c=0; c<N; c++) {
                isEmpty[r][c] = (str.charAt(c) == '1');
            }
        }
    }

    private static void bfs() {
        breakWallCnts = new int[N][N];
        for (int[] arr : breakWallCnts) {
            Arrays.fill(arr, Integer.MAX_VALUE);
        }

        pq.add(new State(0, 0, 0));
        breakWallCnts[0][0] = 0;

        while (!pq.isEmpty()) {
            State state = pq.poll();

            for (int dir=0; dir<4; dir++) {
                int r = state.r + dr[dir];
                int c = state.c + dc[dir];

                if (r < 0 || r == N || c < 0 || c == N) {
                    continue;
                }

                int breakWallCnt = state.breakWallCnt + (isEmpty[r][c] ? 0 : 1);

                if (breakWallCnts[r][c] > breakWallCnt) {
                    breakWallCnts[r][c] = breakWallCnt;
                    if (r==N-1 && c==N-1) {
                        return;
                    }
                    pq.add(new State(r, c, breakWallCnt));
                }
            }
        }
    }

}