모각코 5차(230803)

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

2206번: 벽 부수고 이동하기

---

1. 문제

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

 

 

2. 풀이

일반적으로 풀던 BFS와 비슷한 형태이다. 하지만, 한 가지 조건이 추가되었다면 바로 벽을 한 번 부실 수 있다는 것이다.

 

이것을 활용해서 가장 처음 떠오르는 방법은, 모든 1 중에서 한개만 0으로 바꿔가면서, 도착하는 경우를 계산하는 것이다. 하지만 이 경우의 시간복잡도를 계산해보자. 가로와 세로가 m과 n으로 주어졌다고 하고, (1, 1)과 (m, n)을 제외한 모든 곳이 1로 주어졌다고 하자. 그렇다면 시간복잡도는 O( (mn)^2 )이 된다. 따라서 이 방법으로는 문제를 해결하지 못한다. 그렇다면 어떻게 해결할까??

 

벽을 한번이라도 부셨을 떄와 부시지 못했을 때를 고려해야한다. 그래서 우리는 보통 사용했던 visited(특정 위치를 방문했다면 얼마나 걸렸는지, 방문하지 않았다면 0을 나타내는 배열)의 차원을 늘려야한다. 기존에는 2차원으로 visited[][]를 사용했다.

 

우리는 여기서 한 채널을 더 추가해준다. visited[][][]를 이용하여 가장 마지막에는 0과 1을 나타내며, 0일 때는 아직 벽을 부시지 않은 상태. 1이라면 벽을 부신 상태가 되도록 하여준다.

 

정리하면 우리는 채널을 구분하여 확인해야한다. 만약 우리가 0의 채널(아직 벽을 부시지 않은 상태)이라면 1의 채널로 갈 수 있다. (벽을 부실 수 있다.) 또한 우리가 1의 채널에 있다면, 0의 채널로 갈 수 없다.

 

코드를 통해서 확인해보자.

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 int m;
    static int n;
    static int[][] fourWay = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        int[][] input = new int[m][n];

        System.out.println(BFS(input));
    }

    private static int BFS(int[][] input) {
        Queue<int[]> q = new LinkedList<>();
        int[][][] visited = new int[m][n][2]; // 마지막은 0과 1로 나타내진다.

        q.add(new int[]{0, 0, 0}); // 초기에는 벽을 부시지 않은 상태이므로 마지막 채널에 0을 넣어준다.
        visited[0][0][0] = 1;       // 문제에서는 (1, 1)에서부터 1로 카운트하므로, 소요시간을 1로 넣어준다.

        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            int crush = tmp[2];
            // x와 y는 위치를 나타내며, crush는 0과 1로 0은 아직 벽을 부시지 않은 상태. 1은 벽을 부신 상태이다.

            if(x==m-1 && y == n-1) return visited[x][y][crush];
            // 만약 (m, n)에 도달했다면, 해당 위치까지의 소요 시간을 반환한다.

            for(int i=0; i< fourWay.length; i++){
                int xNew = x + fourWay[i][0];
                int yNew = y + fourWay[i][1];
                // 상하좌우로 도달할 위치를 나타내는 변수가 xNew, yNew이다.

                if(xNew >= 0 && xNew < m && yNew >= 0 && yNew < n) {
                    // 상하좌우로 도달할 위치가 범위 내에 있을 때,

                    if (visited[xNew][yNew][crush] == 0) {
                        // 도달할 위치를 아직 방문하지 않은 상태일 때,

                        if ((input[xNew][yNew] == 1) && (crush == 0)) {
                            // 도달할 위치가 벽(input[xNew][yNew] == 1)이고,
                            // 아직 벽을 부시지 않은(crush == 0) 상태일 때

                            visited[xNew][yNew][1] = visited[x][y][crush] + 1;
                            q.add(new int[]{xNew, yNew, 1});
                            // 해당 위치에 도달하고, 벽을 부신 상태로 넘어간다.

                        }else if(input[xNew][yNew] == 0){
                            // 도달할 위치가 벽이 아닐 때

                            visited[xNew][yNew][crush] = visited[x][y][crush] + 1;
                            q.add(new int[]{xNew, yNew, crush});
                            // 해당 위치에 도달하고, 벽을 부시지 않은 상태를 유지한다.
                        }
                        
                        // 위 상황을 제외한, 아래와 같은 상황들은 다루지 않는다.
                        // * 다음으로 도달할 위치가 벽이고, 이전에 벽을 이미 부신 상태
                        
                    }
                }
            }
        }
        return -1;
        // 그럼에도 불구하고, (m, n)을 도달하지 못했다면 -1을 반환한다.
    }
}

 

3. 결과

 

4. 총평

 - 처음으로 구현했던, 모든 1을 한번씩 반복하면서 0으로 바꾸고, 도달하는 시간을 고려하는 경우는 시간복잡도가 너무 크다.

   이 때는 안된다는 것을 미리 인지하고, 다른 방안을 모색하는 것이 좋을 것 같다.