[Algorithm/Java] 백준 2206번 - 벽 부수고 이동하기

---

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

---

🔍 문제 풀이

풀이 방법

BOJ 17836 공주님을 구해라! 문제와 굉장히 유사하다.

차이점이 있다면, 단 한 번 벽을 부술 수 있다는 것이다.

방문 배열 구조

3차원 배열 v[x][y][crush]는 방문 여부와 최단 거리를 동시에 기록한다.

v[n][m][2]

• v[x][y][0] : (x,y)에 벽을 아직 안 부순 상태로 방문했을 때 거리
• v[x][y][1] : (x,y)에 벽을 이미 1번 부순 상태로 방문했을 때 거리

💻 코드

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

public class Main {
    static int[][] arr;
    static int[][][] v;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // input
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        v = new int[n][m][2]; // [x][y][벽 파괴 여부]

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

        // solve
        int ans = bfs(0, 0);

        // output
        System.out.println(ans);
    }

    static int bfs(int x, int y){
        // 1. 초기화
        Deque<Pos> dq = new ArrayDeque<>();

        // 2. 초기값
        dq.offer(new Pos(x, y, 0));
        v[x][y][0] = 1;

        // 3. 탐색
        while(!dq.isEmpty()) {
            Pos cur = dq.poll();

            // 3.1 종료조건
            if (cur.x == n-1 && cur.y == m-1) {
                return v[cur.x][cur.y][cur.crush]; // 시작점 포함
            }

            // 3.2 4방향, 범위
            for(int d = 0; d<4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

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

                // 벽 파괴 여부
                if (cur.crush == 0) {
                    // 아직 벽을 안부쉈다면
                    if (arr[nx][ny] == 0 && v[nx][ny][0] == 0) {
                        // 벽 부수고 이동
                        v[nx][ny][0] = v[cur.x][cur.y][0] + 1;
                        dq.offer(new Pos(nx, ny, 0));
                    }

                    // 다음 칸이 벽(1)인경우 -> 벽 부수기
                    if(arr[nx][ny] == 1 && v[nx][ny][1] == 0){
                        v[nx][ny][1] = v[cur.x][cur.y][0] + 1;
                        dq.offer(new Pos(nx, ny, 1));
                    }

                }

                // 벽 1번 파괴
                else {
                    // 다음 칸은 반드시 통로(0)이여야만 함
                    if (arr[nx][ny] == 0 && v[nx][ny][1] == 0) {
                        v[nx][ny][1] = v[cur.x][cur.y][1] + 1;
                        dq.offer(new Pos(nx, ny, 1));
                    }
                }
            }
        }
        return -1;
    }

    static class Pos{
        int x, y
        int crush;  // 벽 파괴 여부 (0: 안 부숨, 1: 부숨)
        Pos(int x, int y, int crush) {
            this.x = x;
            this.y = y;
            this.crush = crush;
        }
    }
}