[알고리즘] BFS 너비 우선 탐색 알아보기 ( 백준 2178번 미로 탐색 with 자바 )

 

🤔 BFS ( Breadth First Search ) 너비 우선 탐색?

 

그래프 탐색 알고리즘의 하나로,  루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것입니다.

두 노드 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 쓰입니다.

 

장점

• 출발노드에서 목표노드까지의 최단 경로를 보장한다.

단점

• 노드의 수가 많을수록 탐색 가지가 급격하게 증가하여 보다 많은 기억 공간이 필요하다.
• 해가 존재하지 않는다면 유한 그래프의 경우 모든 그래프를 탐색한 후에 실패한다.

 

✔ 문제유형

• 최단 경로 찾기

 

✔ 시간복잡도

노드가 N이고, 간선의 수가 E인 그래프의 경우

DFS알고리즘과 마찬가지로 인접 행렬로 표현된 경우 O(N^2) 인접 리스트로 표현된경우 O(N+E) 입니다.

[알고리즘] DFS 깊이 우선 탐색 알아보기 ( 백준 2667번 단지번호 붙이기 with 자바)

 

 

 

✔ 탐색 방법

BFS는 DFS가 재귀 호출 or Stack을 사용하는것과 달리, 인접한 정점을 먼저 탐색 해야하기 때문에 선입선출(FIFO)의 특징을 갖고있는 Queue 자료구조를 사용하여 구현합니다.

[자료구조] 큐(Queue)의 이해와 구현 with 자바

 

문제를 풀면서 BFS를 사용해 보겠습니다.

2178번: 미로 탐색

 

🔎 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;

public class Main{
    static int[][] visited;
    static int[][] maze;
    static int n;
    static int m;
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        
        String[] nm = br.readLine().split(" ");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);

        maze = new int[n][m];
        visited = new int[n][m];

        for( int i = 0; i<n; i++){
            String[] arr = br.readLine().split("");
            for( int j = 0; j<m; j++){
                maze[i][j] = Integer.parseInt(arr[j]);
            }
        }

        bfs(0,0);
        
        System.out.print(visited[n-1][m-1]);

	}
    
    static void bfs(int y, int x){
        Queue<int[]> queue = new LinkedList<>();
        visited[y][x] = 1; // 처음 방문한 위치이기 때무에 1로 설정합니다. 
        queue.offer(new int[]{y,x}); // queue에 현제 위치를 추가합니다.

        int[] dx = {1,0,-1,0};
        int[] dy = {0,-1,0,1};
        //queue에 값이 없을때 까지 while문을 실행합니다.
        //즉, 조건에 맞는 경로 끝(행렬의 끝 [n,m])에 도달할때 까지 실행합니다.
        while (!queue.isEmpty()){
            int[] cur = queue.poll();
            int curX = cur[1];
            int curY = cur[0];
            for( int i = 0; i<4; i++){
                int nx = dx[i] + curX;
                int ny = dy[i] + curY;

				//위치의 상,하,좌,우 방향으로 탐색을 해야합니다.
                //하지만 방문을 했거나, index를 벗어난 값은 queue에 추가하지 않습니다.
                if( ny >= 0 && nx >= 0 && ny < n && nx < m ){
                    if( visited[ny][nx] == 0 && maze[ny][nx] == 1){
                    
                    	//현재 위치에 값에 +1 하여 다음 위치에 추가함으로써 값이 증가하게 합니다.
                        visited[ny][nx] = visited[curY][curX] +1;
                        queue.offer(new int[]{ny,nx}); //위치가 조건에 맞다면 queue에 추가하여 다음 탐색을 하게 합니다.
                    }
                }
            }
        }
    }
}

 

 

그림처럼 미로의 길을 지나갈때마다 값이 1씩 증가하여 목적지(n,m)까지의 최소 거리를 구할 수 있습니다.

중간에 돌아가는 길도 있지만 queue를 통해 순차적으로 인접한 위치를 먼저 탐색하기 때문에 이전값을 차례로 더하면서 나아갈 수 있습니다.

 

 

 

 

---

 

📚 Reference : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html