[BOJ - JAVA] 2206 - 벽 부수고 이동하기 (BFS)

# 주소

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

2206번: 벽 부수고 이동하기

# 문제

# 문제 해설 및 코드 리뷰

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 n,m;
    static int[][] arr;
    static class Point{
        int x,y,dis, crash;
        public Point(int x, int y, int dis, int crash){
            this.x = x;
            this.y = y;
            this.dis = dis;
            this.crash = crash;
        }
    }
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    static boolean[][][] visit;
    static int count = Integer.MAX_VALUE;
    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());
        arr = new int[n][m];
        visit = new boolean[2][n][m];
        for(int i = 0; i < n; i++){
            String str = br.readLine();
            for(int j = 0; j < m; j++){
                arr[i][j] = str.charAt(j);
            }
        }
        bfs();
        System.out.println(-1);
    }
    public static void bfs(){
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(0,0,1,0));
        while(!queue.isEmpty()){
            Point now = queue.poll();
            if(now.x == n-1 && now.y == m-1){
                System.out.println(now.dis);
                System.exit(0);
            }
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m){
                    continue;
                }
                int next_dis = now.dis + 1;
                if(arr[nx][ny] == '0'){
                    if(now.crash == 0 && visit[0][nx][ny] == false){
                        queue.offer(new Point(nx,ny,next_dis,0));
                        visit[0][nx][ny] = true;
                    }
                    else if(now.crash == 1 && visit[1][nx][ny] == false){
                        queue.offer(new Point(nx,ny,next_dis,1));
                        visit[1][nx][ny] = true;
                    }
                }
                else if(arr[nx][ny] == '1'){
                    if(now.crash == 0){
                        queue.offer(new Point(nx,ny,next_dis,1));
                        visit[1][nx][ny] = true;
                    }
                }
            }
        }
    }
}

인텔리제이로 처음 백준 문제를 풀었습니다.

근데 하필이면 BFS 중에서도 난이도가 꽤 있는 문제를 골라서 그런지 너무 어려웠습니다.

아직까지 Boolean 타입의 visit 배열을 한 번도 3차원으로 생각해본적이 없는데 이 문제는 이렇게 못하면 못풉니다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static char[][] arr;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    static int n, m;
    static int count = 0;
    static boolean[][] visit;
    static int[][] distance;
    static LinkedList<Point> queue = new LinkedList<>();
    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());
        arr = new char[n][m];
        for(int i = 0; i < n; i++){
            String str = br.readLine();
            for(int j = 0; j < m; j++){
                arr[i][j] = str.charAt(j);
            }
        }
        if(n-1 == 0 && m-1 == 0){
            System.out.println(1);
            System.exit(0);
        }
        visit = new boolean[n][m];
        distance = new int[n][m];
        bfs(0,0, 0, 1);
        System.out.println(-1);
    }
    public static void bfs(int x, int y, int crash, int depth) {
        queue.offer(new Point(x,y));
        visit[x][y] = true;
        while(!queue.isEmpty()){
            Point now = queue.poll();
            if(now.x == n-1 && now.y == m-1){
                System.out.println(depth);
                System.exit(0);
            }
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m){
                    if(visit[nx][ny] == false && arr[nx][ny] == '0'){
                        visit[nx][ny] = true;
                        bfs(nx,ny,crash,depth+1);
                    }
                    else if(arr[nx][ny] == '1'){
                        if(crash == 0){
                            visit[nx][ny] = true;
                            bfs(nx,ny,1,depth+1);
                        }
                    }
                }
            }
        }
    }
}

이 코드는 원래 코든데, 예제 입력문을 그대로 쓰면 전부 정답으로 뜨지만 이상하게 11%에서 틀렸다고 합니다.

그래서 반례를 찾아서 인덱스들을 각각 추적해보니 이상한 인덱스도 방문하고 그러더라고요.

정확하게는.. 벽을 굳이 부수지 않아도 더 빨리 갈 수 있는 방법이 존재할 경우 반례가 생깁니다.

그래서 visit을 3차원으로 선언하여 부쉈을 때와 부수지 않았을 때를 나누어서 생각해야만 했습니다.

그래서 블로그를 찾아봤죠.

대부분 3차원 visit으로 푸시는걸보고 음... 이렇게도 풀 수 있군 하고 배워왔습니다.

그래서 밑의 코드는 정답으로 안나오고 위의 코드만 정답으로 처리됩니다...(어렵다! 골드4문제)

일단 이 문제는 Point에 4개의 인자를 오버라이딩 해야 하므로 따로 class를 생성해주셔야 합니다.

그래서 제일 위에 Point class를 따로 생성해준 뒤 밑의 bfs를 실행하셔야 합니다.

queue에는 일단 0,0,1,0을 넣습니다.

앞의 0,0은 현재 x와 y의 위치이고 세번째 1은 건너간 경로 수, 네번째 0은 충돌했는지 여부입니다.

다른 분들은 boolean타입으로 하시던데 전 그냥 0과 1로 나타내도 충분할 것 같아서 int타입으로 했습니다.

if문에 now.x와 now.y가 각각 n-1, m-1이 되면 now.dis를 그대로 출력하게 합니다. (now.dis가 정답이되는 출력값)

그리고 그렇지 않을 경우 아래의 for문을 실행합니다.

for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m){
                    continue;
                }

nx와 ny가 각각 0보다 작거나 n,m을 초과하면 continue시킵니다. (이렇게 안하면 못풀어요)

이유는 nx와 ny는 새로 생성되는 인덱스들인데, 이것들이 음수가 되거나 n,m보다 초과하면 안되서 그렇습니다.

이후 새로 생성되는 next_dis를 now.dis + 1해준 값으로 선언합니다.

이 next_dis는 계속 갖고갈 것입니다.

그리고 아래의 if문에서 arr[nx][ny] == 0이고 ('0'인 이유는 arr타입이 char이기 때문) now.crash == 0 (충돌하지 않았으며) visit[0][nx][ny] == false (충돌하지 않았을 때 그 인덱스를 방문하지 않음) 일 때 queue에 점을 삽입합니다.

이 점은 nx,ny, 그리고 next_dis(now.dis에 + 1 된 값), 0 ( 충돌하지 않았으므로 crash = 0)을 queue에 넣고 visit[0][nx][ny] = true로 저장합니다.

그러나 만약 now.crash == 1 이고 visit[1][nx][ny] == false 일 경우 (한 번 충돌했고 방문하지 않은 값) 똑같이 queue에 넣고 (이때는 충돌했으므로 crash = 1) visit[1][nx][ny] = true로 저장합니다.

지금까지는 arr == 0일 때의 얘기입니다.

그러니까 원래 위치 0,0에서 인근한 칸으로 이동했을 때 이 arr 값이 0인 곳일 경우를 충돌했는지 여부에 따라 각각 다른 point를 queue에 삽입했습니다.

그렇다면 arr가 1인 곳은 어떨까요? (벽에 부딪혔을 때)

벽에 부딪혔기 때문에 우리는 한 번에 한해서 벽을 허물 수 있습니다. 

그러므로 꼭 now.crash (충돌했는지 여부)가 0인지를 확인해야 하므로 if(now.crash == 0)을 걸고 queue에 점을 또다시 삽입해주셔야 합니다.

이 때의 crash 값은 원래 0이었던 crash였지만 이번에 허물 것이므로 crash = 1이 된 상태로 다시 queue에 삽입하면 되겠습니다. 그리고 visit[1][nx][ny] = true도 꼭 해주셔야 합니다. (crash = 1이므로)

그리고 이미 crash = 1일 때 arr = 1이면 이미 벽을 한 번 허물었는데 또 허물순 없으므로 해당 코드는 따로 실행하지 않습니다.

이를 바탕으로 now.dis는 차곡차곡 +1 되어 쌓이게 되고 출력해주시면 정답이 되겠습니다.

왜 정답률이 저것밖에 안되는지 알 것 같네요. 어렵네요 ㅠㅠ (다른 골드문제보다 더 어려운 듯)

감사합니다.