BOJ G3 2206 벽 부수고 이동하기 JAVA

2206번: 벽 부수고 이동하기

---

문제 읽기

해당 문제는 최단 경로를 구하는 문제라 판단하고 그리 어렵지 않을 것이라 생각했다. 하지만 20퍼센트 쯤에서 본 “틀렸습니다”라는 문구..!! 일단 문제 풀이를 시작해보자.

---

문제 풀기

NxM 크기의 일반적인 맵에 0으로 표현된 빈 칸, 1로 표현된 벽이 존재한다. 0, 0에서 N-1, M-1까지 가는 최단 거리를 찾으면서, 그 중에서 벽 한 개는 뚫을 수 있다.

 

이는 크게 어렵지 않게 생각했다. 최단 거리이기 때문에 DFS와 BFS 중 BFS를 선택했고, 시간 복잡도도 크지 않았다. 그래서 일반적인 BFS를 짜는 대로 코드를 짰고, 거기에 벽을 부술 수 있는 변수 하나를 넣어서 이를 이용해서 벽을 부쉈을 때의 최단 거리도 구했다.

실수한 부분

방문 체크 양날의 검(?)

하지만 처음에는 20퍼센트 쯤에서 틀렸습니다가 나왔다. 맞왜틀??을 외치면서 문제를 다시 찬찬히 읽어 보았다.

 

어느 한 부분이 걸렸다. 벽을 부수고 이동하는 것, 그냥 이동하는 것, 어떻게 보면 칸 마다 이 두 가지 경우가 존재한다. 그리고 나는 visited 배열을 사용해서 방문 체크를 수행하여 재방문을 막았다.

 

처음 코드는 다음과 같다.

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

public class Main {
    static int N, M;
    static int[][] map;
    static class Pos{
        int r, c;
        int depth, broken;
        public Pos(int r, int c, int depth, int broken){
            this.r = r;
            this.c = c;
            this.depth = depth;
            this.broken = broken;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for (int i = 0; i < N; i++){
            String[] line = in.readLine().split("");
            for (int j = 0;j < M; j++){
                map[i][j] = Integer.parseInt(line[j]);
            }
        }

        //bfs
        Queue<Pos> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[N][M];
        q.offer(new Pos(0, 0, 1, 0));
        visited[0][0] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        while(!q.isEmpty()){
            Pos cur = q.poll();

            if (cur.r == N-1 && cur.c == M-1){
                System.out.println(cur.depth);
                return;
            }

            for (int di = 0; di < 4; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc]) continue;

                if (map[nr][nc] == 1){
                    //벽이 있다면
                    //이미 한 번 부셨다면 패스
                    if (cur.broken >= 1) continue;
                    //아니라면 부시고 가기
                    visited[nr][nc] = true;
                    q.offer(new Pos(nr, nc, cur.depth+1, cur.broken+1));
                }
                else{
                    //벽이 없다면 그냥 가기
                    visited[nr][nc] = true;
                    q.offer(new Pos(nr, nc, cur.depth+1, cur.broken));
                }
            }
        }
        System.out.println(-1);
    }
}

 

예를 들어 생각해보자.

 

다음과 같이 예제 그림이 있다.

그런데 이 상태에서 먼저 벽을 뚫고 아래로 내려가 큐에 좌표값이 들어간다. 그러면 저 빨간 동그라미 위치는 이미 방문했기 때문에 더 이상 방문하지 못한다. 즉, 옆으로 돌아 와도 방문하지 못하는 것이다.

 

뭐 최단 거리를 구하는 것이기 때문에 괜찮지 않나? 하는 생각이 들 수도 있다. 위 지도가 전부인 경우에는 가능하다.

 

하지만 다음과 같이 방금 지나온 지도 그 아래에 더더욱 복잡한 지도가 이어져 있다고 가정해보자.

우리는 단 하나의 벽만 뚫을 수 있다. 따라서 위에서 한 번 뚫어버렸다면 아래에서는 절대.. 더 이상 뚫을 수가 없다. 즉, 위에서 뚫고 내려와 이어진 길(파란색 길)로 가는 것보다 아래에서 뚫고 가야 할 경우(노란색 길)가 분명히 많은데 방문 체크 때문에 그걸 잡아내지 못하는 것이다.

 

그래서 방문 체크 배열을 한 차원 더 늘렸다. 기존에는 맵 크기인 NxM이었지만, 한 차원을 더 늘려서 NxMx2로 바꿔주었다. 마지막 차원의 크기를 2로 지정한 이유는 0번째 인덱스에는 벽을 아직 부시지 않은 상태인 좌표, 1번째 인덱스에는 벽을 이미 부신 상태의 좌표를 넣기 위함이다. 이렇게 하면 좌표마다 부신 경우에 대한 최단 거리, 부시지 않은 거리에 대한 최단 거리를 둘 다 저장할 수 있고, 위 예시에서 본 반례를 커버할 수 있다.

 

이렇게 코드를 작성했고 통과했다. 어쩐지 처음에 문제를 너무 빨리 풀었는데 정답률이 높지 않아서 뭐지 했었다.. 문제를 꼼꼼히 다시 읽자!

---

코드

package ps.GraphSearch;

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

public class BOJ_G3_2206_벽부수고이동하기 {
    static int N, M;
    static int[][] map;
    static class Pos{
        int r, c;
        int depth, broken;
        public Pos(int r, int c, int depth, int broken){
            this.r = r;
            this.c = c;
            this.depth = depth;
            this.broken = broken;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for (int i = 0; i < N; i++){
            String[] line = in.readLine().split("");
            for (int j = 0;j < M; j++){
                map[i][j] = Integer.parseInt(line[j]);
            }
        }

        //bfs
        Queue<Pos> q = new ArrayDeque<>();
        boolean[][][] visited = new boolean[N][M][2];
        q.offer(new Pos(0, 0, 1, 0));
        visited[0][0][0] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        while(!q.isEmpty()){
            Pos cur = q.poll();

            if (cur.r == N-1 && cur.c == M-1){
                System.out.println(cur.depth);
                return;
            }

            for (int di = 0; di < 4; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc][cur.broken]) continue;

                if (map[nr][nc] == 1){
                    //벽이 있다면
                    //이미 한 번 부셨다면 패스
                    if (cur.broken >= 1) continue;
                    //아니라면 부시고 가기
                    visited[nr][nc][cur.broken+1] = true;
                    q.offer(new Pos(nr, nc, cur.depth+1, cur.broken+1));
                }
                else{
                    //벽이 없다면 그냥 가기
                    visited[nr][nc][cur.broken] = true;
                    q.offer(new Pos(nr, nc, cur.depth+1, cur.broken));
                }
            }
        }
        System.out.println(-1);
    }
}