[Beakjoon] 백준 2206번 벽 부수고 이동하기 (Java)

2206 벽 부수고 이동하기

 

2206번: 벽 부수고 이동하기

 

난이도 및 유형

난이도 : 골드 3

유형 :   BFS / 그래프 탐색

 

문제

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을 출력한다.

 

 

문제풀이

벽 부수고 이동하기 문제는 가중치가 없는 최단경로를 찾는 문제이기 때문에 BFS를 이용해 탐색하는 방식으로 풀 수 있다. 풀이 시 주의할 점은 경로 당 한 개의 벽을 부수고 이동하는 조건이다. 처음에는 벽을 부수는 조건을 해결하기 위해 모든 칸을 한번씩 0으로 바꾸면서 브루트포스 방식으로 문제를 해결하려 했으나 이 방식은 최악의 경우 (1000 * 1000)의 제곱의 시간복잡도를 갖게된다. 따라서, 시간복잡도를 만족하지 못해 시간초과가 발생할 것이라고 예상했다.

 

그래서 Point 클래스를 만들어 벽을 부수었는지 여부를 확인했다. Point 클래스는 x좌표, y좌표, 현재위치까지 방문한 노드의 수(count), 벽을 부수었는지 여부(crush)를 나타내는 변수들로 구성했다. 그리고 3차원 배열(isVisited[][][])을 활용하여 경로의 벽을 부수었는지 기록했다. isVisited[x][y][0]는 현재까지 벽을 부수지 않고 진행했다는 것을 의미하고 isVisited[x][y][1]은 벽을 부수고 진행했다는 것을 의미한다. isVisited 배열은 Point 배열의 crush 변수를 활용해 결정하도록 했다. 

 

 

[정답코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        final StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        final int n = Integer.parseInt(stringTokenizer.nextToken());
        final int m = Integer.parseInt(stringTokenizer.nextToken());
        final char[][] map = new char[n][m];

        String line;
        for (int i = 0; i < n; i++) {
            line = bufferedReader.readLine();

            for (int j = 0; j < line.length(); j++) {
                map[i][j] = line.charAt(j);
            }
        }

        System.out.println(findShortestRoute(map));
    }

    private static int findShortestRoute(final char[][] map) {
        final int[] dx = {1, 0, -1, 0};
        final int[] dy = {0, 1, 0, -1};

        final Deque<Point> queue = new ArrayDeque<>();
        queue.add(new Point(0, 0, 0, 1));

        final boolean[][][] isVisited = new boolean[map.length][map[0].length][2];
        isVisited[0][0][0] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            if (point.x == map.length - 1 && point.y == map[0].length - 1) {
                return point.route;
            }

            for (int j = 0; j < dx.length; j++) {
                int nextX = point.x + dx[j];
                int nextY = point.y + dy[j];

                if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) {
                    continue;
                }

                if (isVisited[nextX][nextY][point.crush]) {
                    continue;
                }

                if (map[nextX][nextY] == '1') { // 벽인 경우
                    if (point.crush == 0) { // 벽을 부신적 없는 경우
                        isVisited[nextX][nextY][1] = true;
                        queue.add(new Point(nextX, nextY, 1, point.route + 1));
                    }
                }

                if (map[nextX][nextY] == '0') { // 벽이 아닌 경우
                    isVisited[nextX][nextY][point.crush] = true;
                    queue.add(new Point(nextX, nextY, point.crush, point.route + 1));
                }
            } // for
        } // while

        return -1;
    } // findShortestRoute

    static class Point {
        private int x;
        private int y;
        private int crush;
        private int route;

        public Point(final int x, final int y, final int crush, final int route) {
            this.x = x;
            this.y = y;
            this.crush = crush;
            this.route = route;
        }
    }
} // main