[백준] 1261. 알고스팟

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

1261번: 알고스팟

• bfs를 통해 (0, 0)부터 (n-1, m-1)까지 이동하면 된다.
• 다음 노드가 방이면 이어서 이동하고, 다음 노드가 벽이면 부수고 이동한다. 즉, 큐에 벽을 부순 횟수도 담아주어야 한다. 그리고 벽을 부쉈을 때 굳이 1을 0으로 변경해줄 필요가 없으며, 방문처리만 해주면 된다.
• 중요한 점은 우선순위 큐를 사용해서, 벽을 부순 횟수가 적은 노드부터 꺼내야 한다는 것이다.
  • 만약 방문처리를 안해주면 이미 방문한 곳을 계속 방문하므로 무한하게 탐색한다. 따라서 방문처리는 필수이다.
  • 그런데 방문처리를 하면, 하나의 노드로 도착하는 경로의 경우의 수는 단 1개이다. 이미 a라는 경로로 (n-1, m-1) 노드에 도착했으면, (n-1, m-1)에 방문처리가 되어있으므로 b라는 경로로 (n-1, m-1)로 도착하지 못하기 때문이다.
  • 즉, 방문처리를 하면 (n-1, m-1) 노드로 도착하는 여러 경로 중, 벽을 부순 횟수가 적은 경로보다 벽을 부순 횟수가 많은 경로가 먼저 (n-1, m-1) 노드로 도착할 수 있으며, 해당 경로가 유일한 경로가 된다.
  • 따라서 우선순위 큐를 이용하여 벽을 부순 횟수가 적은 경로를 우선으로 탐색하도록 한다. 그러면 (n-1, m-1) 노드로 처음이자 유일하게 도착하는 경로는 벽을 가장 적게 부수는 경로가 된다.

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int m; // 가로
    static int n; // 세로
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int answer;

    public static void main(String[] args) throws IOException {

        // 입력
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String[] str = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(str[j]);
            }
        }

        // 0,0을 시작으로 bfs
        Queue<Node> que = new PriorityQueue<>(); // 우선순위 큐(breakCnt가 적은 노드가 우선)
        visited[0][0] = true;
        que.add(new Node(0, 0, 0));

        while (!que.isEmpty()) {
            Node now = que.poll();

            // 도착점에 도착한 경우 bfs 끝내기 (해당 경로가 가장 적게 벽을 부순 경로임)
            if (now.x == m - 1 && now.y == n - 1) {
                answer = now.breakCnt;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + now.x;
                int ny = dy[i] + now.y;

                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (visited[ny][nx]) continue;

                // 다음 노드가 0이라면 그대로 이동
                if (map[ny][nx] == 0) {
                    visited[ny][nx] = true;
                    que.add(new Node(ny, nx, now.breakCnt));
                }
                // 다음 노드가 1(벽)이라면 부수고 이동 
                if (map[ny][nx] == 1) {
                    visited[ny][nx] = true;
                    que.add(new Node(ny, nx, now.breakCnt + 1));
                }
            }
        }

        System.out.println(answer);
    }

    public static class Node implements Comparable<Node> {

        int y, x;
        int breakCnt;

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

        @Override
        public int compareTo(Node o) {
            return this.breakCnt - o.breakCnt;
        }
    }
}