오늘의 백준 문제

[오늘의 백준 문제] 2206번 벽 부수고 이동하기 - BFS (3차원)

uh1205 2025. 4. 1. 12:43

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

 

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

6 4
0100
1110
1000
0000
0111
0000


첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

15

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

 

아이디어

  • 딱 한 번 벽을 부수는게 가능 → 벽을 부쉈는지 여부 저장 필요
  • DFS로 최단 거리 탐색하면서 벽 2개를 만나면 return

 

첫 번째 시도 - 실패

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

class Main {
    static int N, M;
    static boolean[][] map, visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static int result = Integer.MAX_VALUE;

    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 boolean[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) == '1';
            }
        }

        dfs(0, 0, false, 0);
        System.out.println(result == Integer.MAX_VALUE ? -1 : result);
    }

    static void dfs(int cr, int cc, boolean broken, int dist) {
        if (cr == N - 1 && cc == M - 1) {
            result = Math.min(result, dist + 1);
            return;
        }

        dist++;
        visited[cr][cc] = true;

        for (int d = 0; d < 4; d++) {
            int nr = cr + dr[d];
            int nc = cc + dc[d];

            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            if (visited[nr][nc]) continue;
            if (map[nr][nc]) {
                if (broken) continue;
                broken = true;
            }

            dfs(nr, nc, broken, dist);
        }
    }
}
  • 주어진 테스트 케이스는 통과했지만 이상하게 틀렸다는 결과를 받았다.
  • 도저히 어디서 틀린지 모르겠어서 testcase.ac 도움을 받아서 반례를 찾아봤다.
2 5
00101
00010
  • 어이 없게도 다음과 같은 쉬운 케이스에서 -1을 출력하면서 틀렸다.
  • 보아하니 이미 visited 처리가 되어있어서 탐색해야 하는 경로를 탐색하지 못한 것 같다.
  • 탐색이 끝난 visited는 다시 복구시켜놓자.

 

두 번째 시도 - 시간 초과

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

class Main {
    static int N, M;
    static boolean[][] map, visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static int result = Integer.MAX_VALUE;

    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 boolean[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) == '1';
            }
        }

        dfs(0, 0, false, 1);
        System.out.println(result == Integer.MAX_VALUE ? -1 : result);
    }

    static void dfs(int cr, int cc, boolean broken, int dist) {
        if (cr == N - 1 && cc == M - 1) {
            result = Math.min(result, dist);
            return;
        }
        
        visited[cr][cc] = true;
        
        for (int d = 0; d < 4; d++) {
            int nr = cr + dr[d];
            int nc = cc + dc[d];

            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            if (visited[nr][nc]) continue;
            if (map[nr][nc]) {
                if (broken) continue;
                broken = true;
            }

            dfs(nr, nc, broken, dist + 1);
        }
        
        visited[cr][cc] = false;
    }
    
}
  • 시작 dist를 1로 두고 재귀에서 dist + 1을 호출해줬다.
  • for문으로 4방향 탐색이 끝나면 현재 visited를 false로 바꾸어 줬다.
  • 그런데 이렇게 제출하니 시간 초과가 떴다.
  • 아마도 방문 처리를 초기화함으로써 너무 많은 경우의 수가 발생한 것 같다.
  • 그리고 아직도 통과하지 못하는 테스트 케이스가 있다.
5 2
01
00
11
00
00
  • broken 필드 때문이었다.
  • 이미 broken 필드가 true로 되었기 때문에 맞는 경로로 가도 벽을 부수고 넘어갈 수 없던 것이다.
  • DFS 말고 BFS를 사용해보자.

 

세 번째 시도 - 실패

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

class Main {
    static int N, M;
    static boolean[][] map;
    static int[][][] visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

    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 boolean[N][M];
        visited = new int[N][M][2];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) == '1';
            }
        }

        System.out.println(bfs(0, 0));
    }

    static int bfs(int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r, c});
        visited[r][c][0] = 1;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cr = cur[0];
            int cc = cur[1];

            for (int d = 0; d < 4; d++) {
                int nr = cr + dr[d];
                int nc = cc + dc[d];

                if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
                if (visited[nr][nc][0] > 0) {
                    if (visited[nr][nc][1] == 1 && visited[cr][cc][1] == 0) {
                        visited[nr][nc][1] = 0;
                        continue;
                    }
                }
                if (visited[cr][cc][1] == 1 && map[nr][nc]) continue; // 이미 부수고 갔는데 또 벽을 만난 경우

                visited[nr][nc][0] = visited[cr][cc][0] + 1;
                if (map[nr][nc]) visited[nr][nc][1] = 1; // 벽을 처음 만난 경우

                // 도착한 경우
                if (nr == N - 1 && nc == M - 1) return visited[nr][nc][0];

                q.add(new int[]{nr, nc});
            }
        }

        return -1; // 도착하지 못 한 경우
    }
}
  • 메모리 초과가 떴지만 다음과 같은 케이스도 실패했다.
7 5
00010
11010
00010
01110
00000
11111
11110
  • 유일한 방법은 ㄹ자로 돌아서 벽을 한 번 부수고 15만에 도착하는 것이지만, 이상하게도 11이 출력되었다.

 

올바른 풀이

  • BFS를 이용하여 최단 경로를 탐색하는데, 일반적인 BFS와 다르게, 벽을 부순 상태와 부수지 않은 상태를 구분해야 한다.
  • 따라서 방문 배열을 visited[r][c][벽 부순 여부] 형태로 만들어, 벽을 부쉈을 때와 부수지 않았을 때를 각각 관리한다.
  • 큐에는 (r, c, 벽 부순 여부, 이동 거리) 정보를 저장하여 탐색을 진행한다.
  • 벽을 만났을 때, 벽을 부술 수 있다면(아직 벽을 부순 적이 없다면) 벽을 부수고 이동할 수 있도록 한다.
  • BFS 종료 시, 도착점 (N, M)에 도달하지 못하면 -1을 반환한다.

 

시간복잡도

  • BFS는 한 번 방문한 노드를 다시 방문하지 않으므로 O(N*M)의 시간 복잡도를 갖는다.
  • 벽을 부수는 경우를 추가로 고려해야 하므로, 최악의 경우 O(2 * N * M)이 된다.
  • N, M ≤ 1,000 이므로, 최대 2,000,000의 연산이 발생하여 충분히 수행 가능하다.
import java.io.*;
import java.util.*;

class Main {
    static int N, M;
    static int[][] map;
    static boolean[][][] visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

    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];
        visited = new boolean[N][M][2];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        System.out.println(bfs());
    }

    static int bfs() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 0, 1));
        visited[0][0][0] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();

            // 도착한 경우
            if (cur.r == N - 1 && cur.c == M - 1) {
                return cur.dist;
            }

            for (int d = 0; d < 4; d++) {
                int nr = cur.r + dr[d];
                int nc = cur.c + dc[d];

                if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;

                // 벽을 만나지 않은 경우 - 현재 벽을 부순 상태 유지
                if (map[nr][nc] == 0 && !visited[nr][nc][cur.broken]) {
                    q.add(new Node(nr, nc, cur.broken, cur.dist + 1));
                    visited[nr][nc][cur.broken] = true;
                }

                // 벽을 만난 경우 - 벽을 부수지 않았다면 부수고 통과
                if (map[nr][nc] == 1 && cur.broken == 0 && !visited[nr][nc][1]) {
                    q.add(new Node(nr, nc, 1, cur.dist + 1));
                    visited[nr][nc][1] = true;
                }
            }
        }

        return -1;
    }

    static class Node {
        int r, c, broken, dist;

        Node(int r, int c, int broken, int dist) {
            this.r = r;
            this.c = c;
            this.broken = broken;
            this.dist = dist;
        }
    }
}