너비우선탐색(BFS;Breadth-First Search)

BFS 란?

너비우선탐색(BFS;Breadth-First Search) 알고리즘은 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다.

주로 선입선출 방식은 큐(Queue) 자료구조를 활용하여 구현된다.

모든 간선의 비용이 동일한 조건에서 최단거리를 구하는 문제에 효과적이다.

 

 

BFS의 동작 방식

0. 다음 방문 노드를 저장할 큐와 방문 처리를 위한 visited 변수가 필요하다.

1. 시작 노드를 큐에 삽입하고 방문 처리 한다.

2. 큐가 비어있지 않다면(= 다음 방문 노드가 남아 있다면) 아래 내용을 반복한다.

• 큐의 첫 번째 노드를 꺼내어 현재 노드로 설정.
• 현재 노드 방문 처리.
• 인접 노드를 확인하고, 인접 노드가 아직 방문 되지 않았다면 큐에 삽입.

 

 

 

BFS 구현 예제

[백준/Silver II] 알고리즘 수업 - 너비 우선 탐색 1 - 24444

위 링크의 문제로 예시를 살펴보자. 문제에서 제시하는 입출력 예시의 그래프는 아래와 같다.

이 때, 다음 방문 노드를 저장하는 Queue와 방문 여부를 표시하는 visited는 다음과 같다.

 

Queue : [ 1 ]

node	1	2	3	4
visited	false	false	false	false

 

Queue에 저장된 가장 첫번째 노드를 꺼내고, 현재 노드로 설정한다.

현재 노드를 방문 표시하고 인접한 노드를 탐색한다.

이때, 인접한 노드 2와 4는 방문된 적 없는 노드이므로 Queue에 삽입한다.

 

Queue : [ 2, 4 ]

node	1	2	3	4
visited	true	false	false	false

 

 

다시 Queue에 저장된 가장 첫번째 노드를 꺼내고, 방문 표시한 뒤 인접한 노드를 탐색한다.

이때, 인접한 노드 3과 4는 방문된 적 없는 노드이므로 Queue에 삽입한다.

 

Queue : [ 4, 3, 4 ]

node	1	2	3	4
visited	true	true	false	false

 

 

 

다시 Queue에 저장된 가장 첫번째 노드를 꺼내고, 방문 표시한 뒤 인접한 노드를 탐색한다.

이때, 인접한 노드가 없으므로 Queue에 아무 노드도 추가되지 않는다.

 

Queue : [ 3, 4 ]

node	1	2	3	4
visited	true	true	false	true

 

 

다시 Queue에 저장된 가장 첫번째 노드를 꺼내고, 방문 표시한 뒤 인접한 노드를 탐색한다.

 

Queue : [ 4, 4 ]

node	1	2	3	4
visited	true	true	true	true

 

 

이후 Queue에 남아 있는 노드는 전부 방문한 노드들이므로 인접 노드를 탐색하는 행위를 하지 않는다.

 

아래는 해당 문제를 Java 코드로 구현한 예시이다.

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

public class Solution {

    int[] bfs(int root, ArrayList<Integer>[] map){
        boolean[] visited = new boolean[map.length]; // 노드(index)방문 여부
        int[] order = new int[map.length]; // 노드(index) 순회 순서 저장
        
        
        Queue<Integer> path = new LinkedList<>(); // 다음 방문 노드 Queue
        path.offer(idx); // Queue에 시작 노드 삽입

        int cur, next;
        int cnt = 1; // 순서
        while(!path.isEmpty()){ // path에 저장된 경로를 다 돌아야 함.
            cur = path.poll();
            if(visited[cur]) continue; // 이미 방문한 노드면 continue
            order[cur] = cnt++; // 방문 순서 저장
            visited[cur] = true; // 방문 여부 표시
            // 인접 노드들 중 방문한 적 없고, path에 없는 노드들을 path에 저장
            if(map[cur]==null) continue; // 인접 노드 없으면 continue;
            for(int i = 0; i<map[cur].size(); i++){
            	next = map[cur].get(i);
                if(!visited[next]){
                    path.offer(next);
                }
            }
        }
        return order;
    }
    ...
}