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

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1

15

예제 입력 2

4 4
0111
1111
1111
1110

예제 출력 2

-1

 

접근 방법 🧐

DFS로 푸는 방식을 생각한다면, 벽을 부수고 이동했으면 그 다음 벽은 못 부수게 하면 되고 부수지 않고 이동했으면 다음 벽을 만났을 때 부술 수 있게 하면 된다.

하지만 이는 틀린 접근 방식이다.

특정 칸에 처음 도달했을 때까지의 경로의 길이가 다른 경로를 통해 도달한 길이보다 짧다는 보장이 전혀 없기 때문이다.

그래서 시간 초과가 발생할 수밖에 없다.

 

그렇다면 BFS로 접근해야 한다.

 

우선 유의해둘 것이,

칸마다 방문 체크 하나씩만 하는 방법으로는 풀 수 없다. 어떤 칸에 도달했을 때 "아직 벽을 부술 수 있는 상태"일 수도 있고, "더 이상 벽을 부술 수 없는 상태"일 수도 있다. 큐에 그 상태를 넣은 것만으로 되는 것이 아닌 것이다. 당장 이 칸까지 어떻게든 최단으로 오는 경로만 구했다고 해서, 그 이후의 경로도 최적으로 만들 수 있는 건 아니다.

 

구체적인 예를 들어보자.

1. 현재 칸까지 벽을 부수지 않고 최단 경로로 올 수 있었다고 가정해보자.
   현재 위치에서 목표 칸까지 가는 데 벽을 한 개 부수고 가는 경로가 안 부수고 가는 경로보다 최적 경로라고 해보자.
   그렇다면 지금 내가 벽을 더 부술 수 없는 상태라는 사실을 알고 있어야 하지 않을까?
2. 벽을 안 부수고도 현재 위치까지 도달할 수 있지만, 벽을 부수고 오는 것이 더 짧다고 가정해보자.
   현재 위치에서 목표 칸까지 가려면 무조건 벽을 1개 부숴야만 된다고 해보자.
   비록 현재 위치까지는 벽을 부수고 오는 것이 최적이었지만, 이 상태로는 끝에 아예 도달을 못한다.
   현재 위치까지는 더 멀더라도 벽을 부수지 않고 와야 목표 지점에 도달할 수 있다.

 

그래서 이 문제에서는 BFS에 대해 새로운 테크닉을 요구한다.

단순히 좌표만을 큐에 넣어서 탐색하는 방식에 불과한 것이 아닌, "현재 상태" 자체를 큐에 넣어서 접근해야 한다.

즉, 어떤 좌표에 있는가 뿐만 아니라, "여기까지 오면서 벽을 부순 적이 있는가" 여부를 함께 큐에 저장해서 탐색하고,

각각을 별개로 방문 체크해줘야 하는 문제인 것이다.

visited[x][y]가 아니라, visited[x][y][벽을 부순 적이 있는가?] 가 되어야 하는 것이다.

 

+) 이 문제에서는 같은 칸에 방문하는 경우 벽을 부수지 않은 것이 더 유리하기 때문에 벽을 부쉈는지 여부를 방문 배열에 기록하여 부순 횟수가 더 적을 때만 방문하는 방법도 된다. 하지만 이는 문제의 특성 때문에 이 문제에서만 통하는 그리디 알고리즘이니, 다른 문제에도 함부로 적용하면 안 된다.

 

 

내가 쓴 코드 ✍️

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

public class Main {
    static class Point {
        int x;
        int y;
        int distance;
        boolean destroyedWall;

        public Point(int x, int y, int distance, boolean destroyedWall) {
            this.x = x;
            this.y = y;
            this.distance = distance;
            this.destroyedWall = destroyedWall;
        }
    }

    private static int N, M, answer;
    private static int[] dx = { -1, 0, 1, 0 };
    private static int[] dy = { 0, 1, 0, -1 };
    private static int[][] map;
    private static boolean[][][] visited;

    private static void BFS(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, y, 1, false));

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

            int count = now.distance;
            boolean destroyedWall = now.destroyedWall;

            if (now.x == N && now.y == M) {
                answer = Math.min(answer, count);
            }

            for (int d = 0; d < 4; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];

                if (checkOutOfRange(nx, ny)) continue;
                if (map[nx][ny] == 1 && destroyedWall) continue;

                if (destroyedWall) {
                    if (!visited[nx][ny][1] && map[nx][ny] == 0) {
                        visited[nx][ny][1] = true;
                        q.offer(new Point(nx, ny, count + 1, true));
                    }
                } else {
                    if (!visited[nx][ny][0] && map[nx][ny] == 1) {
                        visited[nx][ny][0] = true;
                        q.offer(new Point(nx, ny, count + 1, true));
                    } else if (!visited[nx][ny][0] && map[nx][ny] == 0) {
                        visited[nx][ny][0] = true;
                        q.offer(new Point(nx, ny, count + 1, false));
                    }
                }
            }
        }
    }

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

        for (int i = 1; i <= N; i++) {
            String line = br.readLine();
            for (int j = 1; j <= M; j++) {
                int value = Character.getNumericValue(line.charAt(j - 1));

                map[i][j] = value;
            }
        }

        answer = Integer.MAX_VALUE;

        visited[1][1][0] = true;
        BFS(1, 1);

        if (answer == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }

    private static boolean checkOutOfRange(int x, int y) {
        return x < 1 || x > N || y < 1 || y > M;
    }
}

 

 

 

구독과 공감♡♡은 블로그 운영에 큰 힘이 됩니다!
긍정적인 댓글 남겨주시면 감사드리며,
보완해야 할 점이 있으면 댓글로 남겨주셔도 좋습니다!