백준 2206 ) 벽 부수고 이동하기

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

 

⏰문제

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

 

 

💡풀이

1. (1,1) -> (N, M) 최단 경로로 이동이라고 해서 BFS를 이용하기로 했다. 

2. 벽을 부쉈는지 안 부쉈는지 현재 상태가 중요하기 때문에 visited를 3차원으로 사용하기로 함.

3. 다음 칸으로 이동했을 때, 다음 칸이 벽인지 아닌지 판단하고 방문했는지 안 했는지 파악해준다. 

큰 틀은 BFS문제를 푸는 것과 같다. 

 

 

 

⌨️ 코드

import java.util.*;
import java.io.*;
/*
0 : 이동O
1 : 벽, 이동X
(1,1) -> (N,M) 최단경로 이동 => BFS
시작하는 칸과 끝나는 칸도 센다.
벽 한 개까지는 부숴도 괜찮다.
부숨. 안 부숨 -> visited[][][]
이동할 수 있는 칸은 상하좌우 1칸씩
 */
public class BOJ_2206_벽부수고이동하기 {
    static int N,M;
    static int[][] map;
    static boolean[][][] visited;
    static int[] mover = {0,0,-1,1};
    static int[] movec = {-1,1,0,0};
    static int ans = -1; //출력 불가능시


    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];

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

        //solve
        BFS();

        //print
        System.out.println(ans);


    }

    static public void BFS(){
        Queue<int[]> q = new LinkedList<>();
        visited = new boolean[N][M][2];
        q.add(new int[]{0,0,1,0}); //0이면 벽 부수지X, 1이면 벽 부숨
        // r,c, dist, 벽을 부쉈는지 아닌지
        visited[0][0][0] = true;

        while(!q.isEmpty()){
            int[] tmp = q.poll();
            if(tmp[0] == N-1 && tmp[1] == M-1){
                ans = tmp[2];
                return;
            }

            for(int m=0; m < 4; m++){
                int nr = tmp[0]+mover[m];
                int nc = tmp[1]+movec[m];

                if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; //범위 벗어나면 못 지나감
                if(map[nr][nc] == 0 && !visited[nr][nc][tmp[3]]){
                    q.add(new int[]{nr, nc, tmp[2]+1, tmp[3]});
                    visited[nr][nc][tmp[3]] = true;
                }
                else {//벽일 때
                    if(tmp[3] == 0 && !visited[nr][nc][tmp[3]+1]){//tmp[3] = 0이면 벽 부순적 없음
                        q.add(new int[]{nr, nc, tmp[2]+1, tmp[3]+1});
                        visited[nr][nc][tmp[3]+1] = true;
                    }
                }
            }
        }
    }
}

 

 

📣 회고

1. 어제에 이어 visited배열을 3차원배열로 이용하는 문제를 풀어봤다. 기존 BFS와 비슷하면서도 조건의 분기가 까다롭다고 생각해서 어려웠던 것 같다. 예를 들어서 아래와 같다.

if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; //범위 벗어나면 못 지나감
                if(map[nr][nc] == 0 && !visited[nr][nc][tmp[3]]){
                    q.add(new int[]{nr, nc, tmp[2]+1, tmp[3]});
                    visited[nr][nc][tmp[3]] = true;
                }
                else {//벽일 때
                    if(tmp[3] == 0 && !visited[nr][nc][tmp[3]+1]){//tmp[3] = 0이면 벽 부순적 없음
                        q.add(new int[]{nr, nc, tmp[2]+1, tmp[3]+1});
                        visited[nr][nc][tmp[3]+1] = true;
                    }
                }

 

기존에는 visited와 map을 위에서 continue를 이용해서 지나치게 했는데 조건 분기가 까다로워졌다.

2. Queue에 자료구조를 담을 때 객체를 사용하기도 했지만 간단하게 int[]를 사용하기도 했다. 문제 풀기에는 간단했지만 사실 int[]를 사용하는 경우에는 다른 사람이 내 코드를 볼 때는 주석 없이 단순에 이해할 수 없을 것 같기도 해서 협업시에는 좋은 것은 아니라고 생각했다. 보다는 명확하게 사용할 수 있는 객체를 사용하는 것이 좋은 것이 아닐까하고 생각하고 있다. 다음에는 객체로 풀어봐야겠다. 

3. 최근에 알고리즘 스터디를 추가로 하고 있다. 일주일에 5문제를 풀기로 했는데, 드디어 1주차를 지나쳐서 폴더를 하나로 몰아 넣었다. 다음주에도 화이팅!

4. 비슷한 문제 

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

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