백준 2206 벽 부수고 이동하기

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

문제해결

기본 bfs에서 벽을 부수고 이동할 수 있다는 조건이 추가된 문제이다. 벽을 부순 적이 있는지 없는지 구분하는 것이 포인트인데 이 부분을 생각하지 못했다. 고민하다가 3차원 배열로 해결할 수 있다는 힌트를 얻고 문제를 해결하였다.

크게 두 가지 경우의 수로 나눌 수 있는데 이전에 벽을 부수지 않은 경우와 벽을 부순 경우이다.

1. 이전에 벽을 부수지 않고 방문한 적이 없는 경우
   • 벽인 경우
     벽을 부수고 거리 +1, 방문처리
   • 벽이 아닌 경우
     거리 +1 , 방문처리
2. 이전에 벽을 부순 적이 있고 방문한 적이 없는 경우
   • 벽이 아닌 경우
     거리 +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;
    }
}