벽 부수고 이동하기(BFS) - 백준 골드3

- 벽 부수고 이동하기 문제

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

 

- 풀이

걸린 시간 : 모름. 그냥 겁나 오래 걸림.

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

public class Main {

    public static int M, N;
    public static ArrayList<Integer> count = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        int[][] graph = new int[M][N];
        int[][][] draw = new int[M][N][2];
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0; i < M; i++){
            String[] str = br.readLine().split("");
            for(int j = 0; j < N; j++){
                graph[i][j] = Integer.parseInt(str[j]);
            }
        }

        graph[0][0] = 1;
        q.offer(new int[]{0, 0, 0});
        draw[0][0][0] = 1;

        while(!q.isEmpty()){
            int[] info = q.poll();
            int y = info[0];
            int x = info[1];
            int w = info[2];

            if(y == M - 1 && x == N - 1){
                count.add(draw[y][x][w]);
                continue;
            }

            bfs(graph, q, draw, y + 1, x, w, draw[y][x][w]);
            bfs(graph, q, draw, y, x + 1, w, draw[y][x][w]);
            bfs(graph, q, draw, y - 1, x, w, draw[y][x][w]);
            bfs(graph, q, draw, y, x - 1, w, draw[y][x][w]);
        }

        if(count.isEmpty()){
            bw.write(String.valueOf(-1));
        } else {
            Collections.sort(count);
            bw.write(String.valueOf(count.get(0)));
        }
        br.close();
        bw.close();
    }

    public static void bfs(int[][] graph, Queue<int[]> q, int[][][] draw, int y, int x, int w, int before){
        if(x < 0 || x >= N || y < 0 || y >= M){
            return;
        }
        if(graph[y][x] == 0 && draw[y][x][w] == 0){
            draw[y][x][w] = before + 1;
            q.offer(new int[]{y, x, w});
            return;
        }
        if(graph[y][x] == 1 && w == 0){
            draw[y][x][w + 1] = before + 1;
            q.offer(new int[]{y, x, w + 1});
        }
    }
}

 

해당 문제는 저번 포스팅 때 못풀었다고 했던 골드 3 문제였다.
정말 많은 고민을 했다.

지하철에서도, 자기 전에도, 씻으면서도,,,

정말 여러 가지 방법으로 구현도 했지만, 제출만 하면

시간 초과, 메모리 초과가 나왔다.

도대체 뭐가 잘못된걸까 하면서, 맞은 사람들의 코드 크기를 보았다.

 

대부분이 2200~2500 정도 되는데, 나는 4000이 넘는 크기였다.

'이거 심하게 뭔가 잘못되었다...' 라는 것을 깨달았다.

하지만 인터넷은 아직까지 보지 않았다.

 

그렇게 2틀이 지나고,,,

접근 방식 자체가 잘못되었다는 것을 인정하고,

인터넷을 통해 어떤 방식으로 푸는지만 보았다. 절대 베끼지 않았다. 맹세코!

 

사실 코드를 보고도 '왜 저 방식으로 저게 풀리지..?' 라는 생각을 했다.

그렇다. 알아먹질 못했다.

그후로 30분이 지났을까, 책상에 엎드려서 계속 생각하는데 머릿속이 번쩍였다.

드디어 왜 풀리는가에 대한 답이 나왔다.

 

내 방식대로 해당 접근 방식을 구현하기 시작했다.

그렇게 20분이 지나고,,, 드디어 성공했다,,,,, 골드3 쉽지 않네,,

이제부터 내가 구현한 방식을 설명하도록 하겠다.

 

1. 문제의 0,1을 저장하는 graph 2차원 리스트
    지나온 칸들의 개수를 표시하는 draw 3차원 리스트
    BFS를 위한 Queue
    최단경로들을 저장하는 count 리스트

draw 3차원 리스트가 핵심이다..!

[M][N][2]로 만들어주면 된다.
마지막이 2인 이유는 벽을 부시지 않은 상태에선 0으로, 부신 상태에선 1로 보내어 BFS를 지속하면 되기 때문이다.

이게 이 문제의 접근 방식이다. 이것을 생각 못해서 2틀을 개고생을...

 

2. 예외처리

그 다음으로 중요한 것은 예외처리이다.

어떤 예외 처리가 중요하냐면, 우리는 (1,1)부터 (M,N)까지 1번의 BFS 진행을 통해 답을 구한다.
왜냐면 최대가 1000 X 1000 이기 때문에 여러 번 반복하면 바로 시간초과가 뜨기 때문이다.

하지만 여기서 visited를 사용하면 안되는 경우가 생긴다.

어떤 경우냐?

이 경우다. 이게 왜 안되냐 싶겠냐만, visited를 쓰게 되면

0 -> 0 -> 0 -> 0 -> 1 (벽뿌심) -> 0 이 방법으로 인해 (2, 3)이 visited = true가 된다.

그러면 정상적인 방법으로 가는 00000 ⤵︎ 00 ← 0(해당 부분에서 visited[2][3] 가 true이기 때문에 return; 처리되어 정상적인 방법으로 (5, 3)에 있는 1을 뿌시러 갈 수가 없다.)

 

그렇기에 visited 방식이 아닌 다른 방식으로 예외 처리를 해야한다.

이거 생각하느라 머리가 지끈거렸다.

한 15분 정도의 고민 끝에 생각해냈다.

if(graph[y][x] == 0 && draw[y][x][w] == 0){
    draw[y][x][w] = before + 1;
    q.offer(new int[]{y, x, w});
    return;
}

이 부분이 되는 이유는

우리는 벽을 부수지 않는 이상, draw[y][x][0]에서만 놀다가, 벽을 깨면 [1]로 내려간다.

내려가서 BFS를 탐색할 때, 우리는 가보지 않은 길을 만나게 될 것이다.

만약 가본 길이라면, 그 경로가 더 짧은 것이므로 탐색할 이유가 없어진다.

 

if(graph[y][x] == 1 && w == 0){
    draw[y][x][w + 1] = before + 1;
    q.offer(new int[]{y, x, w + 1});
}

이 부분은 1이라는 벽을 만나면 [1]로 내려보내는 코드이다.

 

이렇게 해서 해당 문제는 풀리게 되었다.

진짜 어려운 거 같다...

예외에 대해서 깊게 생각해야 하고,

BFS의 개념을 이해하고 풀었다고 해서 모든 문제에서 동일하게 적용되지 않음을 깨달았다.

접근 방식은 다 다르고, 나는 많은 문제들을 풀면서 해당 접근 방식들에 익숙해져야 한다.

내 방식들로 만들면서 말이다.

 

이렇게 안풀린건 처음이라 솔직히 2틀동안 좀 힘들었다...

이제 백트래킹 및 그리디 알고리즘들을 좀 봐야겠다.

그리디 알고리즘은 문제가 다양해서 접근 방식이 스스로 생각해내야 할 것 같은 문제들이라 걱정이다.