백준 2178번: 미로 탐색

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

2178번: 미로 탐색

Source Code : https://github.com/JangAJang/Study/blob/main/백준_그래프와%20순회/미로%20탐색/src/Main.java

요약 : BFS를 쓸 때, 갈 일이 없는 노드를 가지 않음으로 시간소요를 줄일 수 있다. (반복문 -> Queue를 이용해 계산 필요 없는 노드 제거)

 

 

 

BFS문제이다. 학교에서 배운 BFS의 이론에선

1. 같은 레벨의 노드들을 먼저 확인한다. 

2. 이후에 리프 노드(다음단계)를 확인한다. 

3. 다시 리턴한다.

라는 방식으로 문제를 풀었다. 

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

public class Main {

    static int[] x_case = {-1, 0, 1, 0};
    static int[] y_case = {0, -1, 0, 1};
    static int[][] arr;
    static long[][] bfs;
    static boolean[][] visited;
    static int x;
    static int y;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        arr = new int[x+1][y+1];
        bfs = new long[x+1][y+1];
        visited = new boolean[x+1][y+1];
        for(int i=1; i<=x; i++){
            String s = br.readLine();
            for(int j=1; j<=y; j++){
                arr[i][j] = Character.getNumericValue(s.charAt(j-1));
                bfs[i][j] = Integer.MAX_VALUE;
                visited[i][j] = false;
            }
        }
        bfs[1][1] = 1;
        bfs(1, 1);
        System.out.println(bfs[x][y]);
    }

    public static void bfs(int a, int b){
        visited[a][b] = true;
        if(a == x && b == y) return;
        for(int i=0; i<4; i++){
            int X = a + x_case[i];
            int Y = b + y_case[i];
            if(X>0 && X <= x && Y > 0 && Y <= y){
                if(arr[X][Y] == 1 && !visited[X][Y]){
                    bfs[X][Y] = Math.min(bfs[X][Y], bfs[a][b] + 1);
                }
            }
        }
        for(int i=0; i<4; i++){
            int X = a + x_case[i];
            int Y = b + y_case[i];
            if(X>0 && X <= x && Y > 0 && Y <= y){
                if(arr[X][Y] == 1 && !visited[X][Y]){
                    bfs(X, Y);
                }
            }
        }
        visited[a][b] = false;
    }
}

문제는 시간 초과가 떴다. 왜일까 생각해보니, 반복문으로 진행하면 하나의 문제가 있음을 느꼈다. 

분명 길은 1이어야 하는데, 0도 다 반복문의 특성상 확인을 해야한다. 

 

그래서, 다른 방식의 BFS를 구상해야함을 느꼈다. 

 

실제로 찾아보며 배운 것은, bfs는 재귀로 동작하지 않는다. 대부분 사람들이 Queue를 쓴다는 것이었다. (여태 난 무얼 했는가..!

그래서 큐의 특성을 이용해 다시 구상해보았다. 

1. 시작 노드를 큐에 넣는다. 
2. 시작 노드를 visited = true로 한다. 
3. 반복문을 시작시킨다. (while(!queue.isEmpty())
4. 큐에서 노드를 하나 꺼낸 다음, 거기에서 갈 수 있는 노드들을 탐색한다. (값이 1이면서 바로 인접 칸인 경우)
5. 갈 수 있는 노드의 거리 = 큐에서 뺀 노드의 거리 + 1, 해당 노드를 큐에 넣는다. 큐에 넣을때 visited = true로 한다. 

이 때 몇가지 포인트가 있는데, visited = false이거나, 노드의 주소가 주어진 미로의 크기를 벗어날 때, 그리고 값이 0일 때 이다. 

 

이러한 점을 고려해서 코드를 다시 짜보았다. 

Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{1, 1});
while(!queue.isEmpty()){
    int[] point = queue.poll();
    for(int i=0; i<4; i++){
        int a = point[0] + x_case[i];
        int b = point[1] + y_case[i];
        if(a < 1 || b < 1 || a > x || b > y) continue;
        if(visited[a][b] || arr[a][b] == 0)continue;
        queue.add(new int[]{a, b});
        arr[a][b] = arr[point[0]][point[1]] + 1;
        visited[a][b] = true;
    }
}

bfs를 이렇게 구현하고 실행을 했을 때, 결국 맞는 값을 구할 수 있었다.