[JAVA] 미로찾기 문제 풀 땐 DFS보다 BFS with Queue

 

 

오늘의 문제는 미로 찾기!!

미로 찾기는 ①  출발점에서 도착점까지 가는 최단거리를 찾는 문제이거나 

② 출발점에서 도착점까지 갈 수 있는 경로의 개수를 세거나 하는 문제 인데 

 

이번 백준 2178번 문제는 최단거리를 찾는 문제이다. 

 

 

 

 

처음에 DFS로 문제를 풀었다. 

 

DFS 문제 풀이

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

public class beakjoon_2178 {

    static int[][] miro;
    static boolean[][] visit;
    static int min;
    static int n;
    static int m;

    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());

        miro = new int[n][m];
        visit = new boolean[n][m];
        min = n*m;

        for(int i=0; i<n; i++){
            String str = br.readLine();
            for(int j=0; j<m; j++){
                miro[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
            }
        }

        visit[0][0] = true;
        dfs(0,0,1);

        System.out.println(min);

    }

    static void dfs(int i, int j, int length){

        if(i==n-1 && j==m-1){
            if(min>length){
                min = length;
            }
        }
        else{


            if(j+1<m){  //우
                if(miro[i][j+1]==1 && !visit[i][j+1]){
                    visit[i][j+1] = true;
                    dfs(i, j+1, length+1);
                    visit[i][j+1] = false;
                }
            }

            if(i+1<n){ //하
                if(miro[i+1][j]==1 && !visit[i+1][j]){
                    visit[i+1][j] = true;
                    dfs(i+1, j, length+1);
                    visit[i+1][j] = false;
                }

            }

            if(i-1>=0){ //상
                if(miro[i-1][j]==1 && !visit[i-1][j]){
                    visit[i-1][j] = true;
                    dfs(i-1, j, length+1);
                    visit[i-1][j] = false;
                }
            }

            if(j-1>=0){ //좌
                if(miro[i][j-1]==1 && !visit[i][j-1]){
                    visit[i][j-1] = true;
                    dfs(i, j-1, length+1);
                    visit[i][j-1] = false;
                }
            }
        }



    }
}

 

 

 

그런데 시간초과가 나버렸땅! 😣

 

이 문제는 DFS가 아닌 BFS로 접근해야하는 문제였다. 

우선 DFS와 BFS 탐색 방식의 차이는 이렇다 

 

 

 

 

 

🤔 DFS와 BFS의 탐색 방식 차이

• DFS (깊이 우선 탐색):
  • 한 경로를 끝까지 탐색한 후, 다시 돌아와 다른 경로를 탐색한다.
  • 재귀 호출이나 스택을 사용해 "백트래킹(backtracking)"하며 경로를 탐색한다.
  • 경로를 끝까지 탐색해야 하므로 비효율적인 경우가 많다.
• BFS (너비 우선 탐색):
  • 가까운 노드부터 차례대로 탐색하며, 같은 레벨의 노드를 모두 확인한 후 다음 레벨로 이동한다.
  • 최단 경로를 자연스럽게 찾으며, 탐색 깊이를 최소화한다.

 

 

😯 그래서 DFS가 더 오래 걸리는 이유

1. 불필요한 경로 탐색:
   • DFS는 모든 경로를 끝까지 탐색하기 때문에, 최적의 경로를 찾더라도 다른 모든 경로를 탐색해야 한다.
   • 특히, 그래프의 노드가 많고 경로가 복잡할수록 DFS는 비효율적이다.
2. 백트래킹의 비용:
   • DFS는 잘못된 경로로 깊이 들어간 뒤, 다시 되돌아오는 과정(백트래킹)이 필요한데, 이 과정은 반복적으로 호출 스택을 사용하므로 시간 소모가 크다.
3. 최단 경로를 바로 찾지 못함:
   • BFS는 가까운 노드를 먼저 탐색하므로 최단 경로를 바로 찾을 가능성이 크다.
   • 반면 DFS는 임의의 깊은 경로로 탐색하기 때문에 최단 경로를 바로 찾지 못할 가능성이 높다.😯😯😯😯

 

 

 

😊 BFS로 미로찾기 풀기 

이는 거리를 저장하는 배열이다.  이 칸을 bfs로 하나씩 채워주는 것이 이 해답의 포인트!!

 

[0,0]부터 Queue에 넣은 뒤 하나씩 꺼내서 다음을 반복한다. 

   ▶️ 상하좌우 중 1인 칸을 탐색하여 거리를 현재에서 +1해서 저장하고 해당 칸을 Queue에 넣어준다. 

 

그럼 최종적으로 [n-1][m-1]인 칸의 거리가 최단 거리가 된다. 

 

 

 

 

 

BFS 문제 풀이

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 beakjoon_2178 {

    static int[][] miro;
    static int[][] distance;
    static int min;
    static int n;
    static int m;

    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());

        miro = new int[n][m];
        distance = new int[n][m];
        min = n*m;

        for(int i=0; i<n; i++){
            String str = br.readLine();
            for(int j=0; j<m; j++){
                miro[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
            }
        }

        distance[0][0] = 1;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0}); //**큐안에 배열(좌표값)

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();

            int i = cur[0];
            int j = cur[1];

            if (i - 1 >= 0) {  //상
                if (miro[i - 1][j] == 1 && distance[i - 1][j] == 0) {
                    distance[i - 1][j] = distance[i][j] + 1;
                    queue.add(new int[]{i - 1, j});
                }
            }

            if (i + 1 < n) {  //하
                if (miro[i + 1][j] == 1 && distance[i + 1][j] == 0) {
                    distance[i + 1][j] = distance[i][j] + 1;
                    queue.add(new int[]{i + 1, j});
                }

            }

            if (j - 1 >= 0) {  //좌
                if (miro[i][j - 1] == 1 && distance[i][j - 1] == 0) {
                    distance[i][j - 1] = distance[i][j] + 1;
                    queue.add(new int[]{i, j - 1});
                }
            }

            if (j + 1 < m) {  //우 
                if (miro[i][j + 1] == 1 && distance[i][j + 1] == 0) {
                    distance[i][j + 1] = distance[i][j] + 1;
                    queue.add(new int[]{i, j + 1});
                }
            }


        }


        System.out.println(distance[n-1][m-1]);

    }

}

 

 

 

 

 

 

 

 

 

 

 

 

 

오예!

 

 

앗 만약 출발점에서 도착점까지 갈 수 있는 경로의 개수를 묻는 문제가 나온다면 

방문을 확인하는 과정을 생략하고 도착지에 도달할 때마다 COUNT+1을 해주면 될 것 같다!