[Algorithm] 백준_2206 벽 부수고 이동하기 java

문제

N * M의 행렬에서 0은 이동 가능한 곳, 1은 벽을 나타낸다. 이때 (1, 1)에서 (N, M)까지 최단 거리로 이동하려고 한다. 이동하면서 딱 한 번의 벽을 부수고 이동할 수 있고, 안 부시고 이동해도 된다. 이때 최단 경로를 구해내는 프로그램을 작성해라.

풀이

최단 거리를 구해야하기 때문에 BFS로 풀이했다. 이 문제에서 중요했던 건, 딱 한 번만 벽을 부술 수 있다는 점이었다.
그래서 원래는 boolean 변수로 벽을 부쉈는지를 체크했었는데 실핻 도중에 진짜 딱 한번만 부숴짐ㅜㅜ..

그래서 3차원 boolean 배열로 부쉈을 때와 안부쉈을 때의 방문 체크를 분리했다.
또 객체에 벽을 부순 적 있는지와 이동 거리를 함께 저장하며 기록했다.

다음에 가야하는 위치가

• 벽인 경우
  • 이전에 부신 적이 없고
  • 방문한 적이 없는 배열이면 방문
• 벽이 아닌 경우
  • 방문한 적이 없는 배열이면 방문

소스 코드

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

public class BOJ_2206 {
    static int N;
    static int M;
    static int[][] map;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static boolean[][][] visited;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        map = new int[N+1][M+1];
        visited = new boolean[N+1][M+1][2];

        for (int i = 1; i <= N; i++) {
            input = br.readLine().split("");
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(input[j-1]);
            }
        }

        bfs(1, 1);
    }

    static void bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, 0, 1));

        visited[x][y][0] = true;
        visited[x][y][1] = true;

        while (!q.isEmpty()) {
            Point p = q.poll();

            if (p.x == N && p.y == M) {
                System.out.println(p.count);
                return;
            }

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

                if (nx <= 0 || ny <= 0 || nx > N || ny > M) continue;

                if(map[nx][ny] == 1) { //벽
                    if (breakWall == 0 && !visited[nx][ny][1]) { //벽을 부신 적 없음
                        visited[nx][ny][1] = true;
                        q.add(new Point(nx, ny, 1, count + 1));
                    }
                } else { //빈 칸
                    if(!visited[nx][ny][breakWall]) {
                        q.add(new Point(nx, ny, breakWall, count + 1));
                        visited[nx][ny][breakWall] = true;
                    }
                }
            }
        }

        System.out.println(-1);
    }

    static class Point {
        int x; int y;
        int breakWall;
        int count;

        public Point(int x, int y, int breakWall, int count) {
            this.x = x;
            this.y = y;
            this.breakWall = breakWall;
            this.count = count;
        }
    }
}