P2206 벽 부수고 이동하기

문제

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

알고리즘

bfs를 이용하여 탐색을 진행했다. 일반적인 bfs와 다른 점은 특정 좌표에 방문했을 때 지금까지 벽을 부순 횟수가 다를 수 있다는 점이다. 예를 들어 벽을 부수지 않은 상태에서 [2, 3] 에 도달했고 벽에 막힌 상황이라면, 그 벽을 한 번 부수고 벽 너머로 이동할 수 있다. 하지만 벽을 부순 상태에서 [2, 3]에 도달했고 벽에 막힌 상황이라면 더 이상 탐색하지 못한다. 따라서 벽을 부순 횟수마다 방문 배열을 새롭게 만들어서 탐색에 활용해야 한다.

bfs를 하기 위해 Queue 자료구조를 선언하고 Queue에는 크기 4의 int 배열을 저장한다. int 배열의 구성은 다음과 같다.

{r인덱스, c인덱스, 지금까지 온 거리, 부실 수 있는 횟수}

Queue<int[]> q = new LinkedList<>();
//{r인덱스, c인덱스, 지금까지 온 거리, 부실 수 있는 횟수}
q.add(new int[] {r, c, 1, 1});

4방 탐색을 하면서 경로를 탐색하다가 벽을 만나는 경우에는 두 가지로 분기한다.

만약 벽을 만났는데 벽을 부술 수 있는 횟수가 한 번 남은 경우에는 int 배열의 3번째 인덱스를 하나 줄여서 Queue에 넣는다.
만약 벽을 만났는데 벽을 부술 수 있는 횟수가 없다면 해당 경로는 더 이상 탐색이 불가능하므로 탐색하지 않는다.

총 2개의 방문 체크 배열이 필요하다. 하나는 벽을 부수지 않은 상태에서 경로를 체크하는 것이고, 또 다른 하나는 벽을 부순 상태에서 경로를 체크하기 위함이다. 이는 3차원 배열로 구성했으며, 벽을 부수지 않은 상태는 visited[1]에 저장된 2차 배열에 방문 체크를 하게 된다. 반대로 벽을 부순 상태에서는 visited[0]에 저장된 2차 배열에 방문 체크를 하게 된다.

for (int i = 0; i < 4; i++) {
    int newR = curR + dr[i];
    int newC = curC + dc[i];

    if (1 <= newR && newR <= N && 1 <= newC && newC <= M) {
        if (map[newR][newC] == 0 && visited[count][newR][newC] == false) {
            visited[count][newR][newC] = true;
            q.add(new int[] {newR, newC, dist + 1, count});
        } else if (map[newR][newC] == 1 && count > 0) {
            if (visited[count - 1][newR][newC] == false) {
                visited[count - 1][newR][newC] = true;
                q.add(new int[] {newR, newC, dist + 1, count - 1});
            }
        }
    }
}

코드

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

public class Main {
    static final int[] dr = {0, 1, 0, -1};
    static final int[] dc = {1, 0, -1, 0};

    static int N, M;
    static int[][] map;
    static boolean[][][] visited;

    public static void main(String[] args) throws Exception {
        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[2][N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String line = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = line.charAt(j - 1) - '0';
            }
        }

        System.out.println(getPath(1, 1));
    }

    public static int getPath(int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        //{r인덱스, c인덱스, 지금까지 온 거리, 부실 수 있는 횟수}
        q.add(new int[] {r, c, 1, 1});
        visited[1][r][c] = true;

        while(!q.isEmpty()) {
            int[] current = q.poll();
            int curR = current[0]; int curC = current[1]; int dist = current[2]; int count = current[3];

            if (curR == N && curC == M) return dist;

            for (int i = 0; i < 4; i++) {
                int newR = curR + dr[i];
                int newC = curC + dc[i];

                if (1 <= newR && newR <= N && 1 <= newC && newC <= M) {
                    if (map[newR][newC] == 0 && visited[count][newR][newC] == false) {
                        visited[count][newR][newC] = true;
                        q.add(new int[] {newR, newC, dist + 1, count});
                    } else if (map[newR][newC] == 1 && count > 0) {
                        if (visited[count - 1][newR][newC] == false) {
                            visited[count - 1][newR][newC] = true;
                            q.add(new int[] {newR, newC, dist + 1, count - 1});
                        }
                    }
                }
            }
        }
        return -1;
    }
}

저작자표시 (새창열림)