白準2206壁を破壊して移動

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

トラブルシューティング

これは基本bfsにおいて壁を破り移動できる条件を増やした問題である.壁にぶつかったかどうかを区別するのがポイントで、意外でした.考えた結果,3次元配列で解決できるヒントが得られ,問題が解決された.
大きく分けると、以前は壁を破らなかった場合と壁を破らなかった場合があります.

壁を破ったことはありません

壁
破壁後距離+1、オンサイトサービス

非

壁
距離+1、オンサイトサービス

以前に壁を壊し、壁にアクセスしたことがない場合
非

壁
距離+1、オンサイトサービス

ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * (1,1) -> (N,M) 최단 경로 구하기
 * 만약, 이동이 불가능할 경우 -1 출력
 * 조건) 벽을 부수고 이동할 경우 거리가 짧아진다면 1개의 벽을 부술 수 있음
 * 한 번도 벽을 부순 적이 없다면, 벽 부수고 이동 가능
 * 한 번이라도 벽을 부순 적이 있다면, 벽 부수고 이동 불가능
 */

public class b2206 {
    static int n; // 행
    static int m; // 열
    static int[][] map;
    static boolean[][][] check;
    static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    static Queue<Point> queue;

    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];
        // 방문 여부와 벽 부순 여부를 구분하기 위해 3차원 배열로 선언
        // 0이면 벽을 부순 적이 없음
        // 1이면 벽을 부순 적이 있음
        check = new boolean[n][m][2];
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }
        bfs(0, 0);
    }

    public static void bfs(int x, int y) {
        queue = new LinkedList<>();
        // 시작점도 포함
        queue.add(new Point(x, y, 1, 0));

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            // 도착지점을 만나면 종료
            if (point.x == n - 1 && point.y == m - 1) {
                System.out.println(point.cnt);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nx = point.x + dx[i];
                int ny = point.y + dy[i];
                /**
                 * 1. 벽을 부순 적이 없는 경우
                 *   - 벽인 경우
                 *   => 벽을 부수고 거리 +1, 방문처리
                 *   - 벽이 아닌 경우
                 *   => 거리 +1, 방문처리
                 * 2. 벽을 부순 적이 있는 경우
                 *   - 벽이 아닌 경우만 체크
                 *   - 거리 +1, 방문처리
                 */
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    // 이전에 벽을 부순 적이 없고 방문하지 않았다면
                    if (point.destroyed == 0 && !check[nx][ny][0]) {
                        // 벽인 경우
                        if (map[nx][ny] == 1) {
                            // 벽을 부수고 거리 +1, 방문처리
                            queue.add(new Point(nx, ny, point.cnt + 1, point.destroyed + 1));
                            check[nx][ny][1] = true;
                        } else { // 벽이 아닌 경우
                            queue.add(new Point(nx, ny, point.cnt + 1, point.destroyed));
                            check[nx][ny][0] = true;
                        }
                    // 이전에 벽을 부순 적이 있고 방문하지 않았다면
                    } else if (point.destroyed == 1 && !check[nx][ny][1]) {
                        if (map[nx][ny] == 0) { // 벽이 아닌 경우만 체크
                            queue.add(new Point(nx, ny, point.cnt + 1, point.destroyed));
                            check[nx][ny][1] = true;
                        }
                    }
                }
            }
        }
        System.out.println(-1);
    }
}

class Point {
    int x;
    int y;
    int cnt;
    int destroyed;

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