[백준] 2206 : 벽 부수고 이동하기 (JAVA/자바)

문제

BOJ 2206 : 벽 부수고 이동하기 - https://www.acmicpc.net/problem/2206

풀이

상하좌우를 확인해서 BFS 로 진행한다. 벽을 최대 한 번 까지 부술 수 있기 때문에, 다음 갈 위치가 벽일 경우

• 한번도 벽을 부순적이 없다면 -> 벽을 부수고 이동한다.
• 한번이라도 벽을 부순적이 있으면 -> 갈 수 없다.

위 조건만 생각해서 처리하면 된다고 생각했다. 하지만 벽을 부수고 간 경우가 특정 위치에서 먼저 도달하지만 최종적으로 부수지 않고 간 경우가 더 빠를 수 있다는 반례가 존재하기 때문에 일반적인 이중배열 visit 처리로는 풀이가 불가했다. 아래 반례를 실행해보면 이해할 수 있다.

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

그래서 visited를 3중 배열로 만들어서, 벽을 부수고 탐색하는 경우와 부수지 않고 탐색하는 경우를 따로 처리해주었다. visited[n][m][0]은 벽을 한번도 안부순 애들이 탐색한 경우, visited[n][m][1]은 벽을 한번 부수고 탐색한 경우이다.

BFS 탐색 조건은 다음과 같다.

• 벽이 아니면
  • 부신 벽이 여태까지 없었으면 -> visited[?][?][0] 방문 처리 + queue에 넣음
  • 벽을 한번 부신 적이 있으면 -> visited[?][?][1] 방문 처리 + queue에 넣음
• 벽이면
  • 한번도 벽을 부신 적이 없으면 부수고 -> visited[?][?][1] 방문 처리 + queue에 넣음

코드

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


public class Main {
    static class Loc{
        int i;
        int j;
        int cnt;
        boolean destroyed;

        public Loc(int i, int j, int cnt, boolean d) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
            this.destroyed = d;
        }
    }


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

        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        char[][] map = new char[n][m];
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = input.charAt(j);
            }
        }


        Queue<Loc> q = new LinkedList<>();
        q.add(new Loc(0, 0, 1, false));

        int[] mi = {0, 0, -1, 1};
        int[] mj = {-1, 1, 0, 0};

        boolean[][][] visited = new boolean[n][m][2];

        while (!q.isEmpty()) {
            Loc now = q.poll();

            if (now.i == n - 1 && now.j == m - 1) {
                System.out.println(now.cnt);
                return;
            }

            for (int d = 0; d < 4; d++) {
                int ni = now.i + mi[d];
                int nj = now.j + mj[d];

                if(ni<0 || ni>=n || nj<0 || nj>=m) continue;

                int next_cnt = now.cnt+1;

                if(map[ni][nj]=='0'){ // 벽이 아니면
                    if(!now.destroyed && !visited[ni][nj][0]) { // 부신 벽이 여태까지 없었으면
                        q.add(new Loc(ni, nj, next_cnt, false));
                        visited[ni][nj][0] = true;
                    }else if(now.destroyed && !visited[ni][nj][1]){ // 벽을 한번 부신 적이 있으면
                        q.add(new Loc(ni, nj, next_cnt, true));
                        visited[ni][nj][1] = true;
                    }

                }else if(map[ni][nj]=='1'){ // 벽이면

                    if(!now.destroyed){ // 한번도 벽을 부순적이 없다면 부순다~
                        q.add(new Loc(ni, nj, next_cnt, true));
                        visited[ni][nj][1] = true;
                    }
                    // 한번 부순 적이 있다면 또 부수고 갈 수 없기 때문에 pass
                }
            }

        }

        System.out.println(-1);
    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 너비 우선 탐색
✔ 난이도 - 🟡 Gold 4

🤦‍♀️ 오늘의 메모

• BFS는 한 위치에 먼저 도착했을 경우 무조건 더 빠르다고 볼 수 있다! 라고 알고있지만 이렇게 예외적인 케이스(벽을 부술 수 있는 경우)에 방문 처리를 어떻게 해줘야할지 고민이 필요했다.. visited 배열을 3중 배열로 만들어 각각 처리하는 방법이 있다는 것이 생소하고 신기했다. 정말 문제 풀이 방법의 끝은 없는 것 같다!

참고 사이트

2206번 질문게시판