[백준 | Java] 2206 벽 부수고 이동하기

내 풀이

최단 경로로 이동하므로 BFS를 사용한다.

이 문제의 핵심은 모든 위치를 방문할 때, 벽을 부순 적이 있는지 여부를 함께 고려해 탐색해야 한다는 것이다.

따라서 객체를 활용해 벽을 부순 여부와 최단거리를 저장하고, 방문 확인 배열을 삼중배열로 받아 각 위치를 벽을 부순 상태로 방문했는지 아닌지를 저장한다.

BFS 탐색 과정은 다음과 같다.

1. 이동할 위치가 벽이 아닌 경우
   a. 벽을 부수지 않은 상태에서 방문한 적이 없으면 큐에 추가하고 해당 위치를 방문 처리 (부순 여부 false로 전달)
   b. 벽을 이미 부쉈던 상태에서 방문한 적이 없으면 큐에 추가하고 해당 위치를 방문 처리 (부순 여부 true로 전달)
2. 이동할 위치가 벽인 경우
   a. 벽을 부수지 않은 상태에서 방문한 적이 없으면 큐에 추가하고 해당 위치를 방문 처리 (부순 여부 true로 전달)
3. n, m 위치에 닿을 때 까지 위의 과정 반복

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

public class Main {
    static int n, m;
    static int[][] map;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static class Person {
        int x, y, dis;
        boolean isBroken;

        public Person(int x, int y, int dis, boolean isBroken) {
            this.x = x;
            this.y = y;
            this.dis = dis;
            this.isBroken = isBroken;
        }
    }

    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[n][m];

        for (int i = 0; i < n; i++) {
            String tmpStr = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = tmpStr.charAt(j) - '0';
            }
        }

        int result = bfs();
        System.out.println(result);
    }

    static int bfs() {
        boolean[][][] visited = new boolean[n][m][2];
        Queue<Person> queue = new LinkedList<>();
        queue.offer(new Person(0, 0, 1, false));
        // visited[i][j][0] => [i][j]위치의 벽을 부수지 않고 방문한 경우
        // visited[i][j][1] => [i][j]위치의 벽을 부수고 방문한 경우
        visited[0][0][0] = true;

        while (!queue.isEmpty()) {
            Person person = queue.poll();
            int x = person.x;
            int y = person.y;
            int dis = person.dis;
            boolean isBroken = person.isBroken;

            if (x == n - 1 && y == m - 1) return dis;

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

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

                if (map[nx][ny] == 0) {
                    // nx, ny가 벽이 아닐 때
                    if (!isBroken && !visited[nx][ny][0]) {
                        // 벽을 부순적이 없고, nx, ny의 벽을 부수지 않고 방문한 적이 없을 때
                        queue.offer(new Person(nx, ny, dis + 1, false));
                        visited[nx][ny][0] = true;
                    } else if (isBroken && !visited[nx][ny][1]) {
                        // 벽을 부순적이 있고, nx, ny의 벽을 부수고 방문한 적이 있을 때
                        queue.offer(new Person(nx, ny, dis + 1, true));
                        visited[nx][ny][1] = true;
                    }
                } else if (map[nx][ny] == 1 && !isBroken) {
                    // nx, ny가 벽이고, 벽을 부순 적이 없을 떄
                    queue.offer(new Person(nx, ny, dis + 1, true));
                    visited[nx][ny][1] = true;
                }
            }
        }
        return -1;
    }
}