[알고리즘] BFS(너비 우선 탐색)

1. 개념

주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것을 그래프 순회라고 한다. BFS는 그래프를 순회하는 방법 중 하나이다. 

BFS는 시작 노드부터 출발해서 시작 노드와 인접한 것들을 모두 방문한다. 그리고 다음 노드를 방문하고, 그 노드와 인접한 것들을 모두 방문한다.

 

2. 예시

위와 같은 그래프를 BFS로 방문하면 다음과 같다. 방문 우선순위는 숫자 오름차순이다.

1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7

 

3. 특징

• 선입선출 탐색이다
• 큐 자료구조를 이용한다
• 시간복잡도는 O(노드 수 + 에지 수)이다.
• 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다

 

4. 코드

1) 연결리스트 만들기

// 연결리스트 만들기
List<Integer>[] adj = new List[n+1];
        
for(int i = 1; i<=n; i++){
    adj[i] = new ArrayList<Integer>();
}
for(int i = 0; i<wires.length; i++){
    int start = wires[i][0];
    int end = wires[i][1];
    adj[start].add(end);
    adj[end].add(start);
}

// BFS
public int bfs(int target){
        boolean[] visited = new boolean[N+1];
        Queue<Integer> q = new LinkedList<Integer>();
        int count = 0;
        
        q.offer(target);
        
        while(!q.isEmpty()){
            int val = q.poll();
            visited[val] = true;
            count++;
            for(int num : adj[val]){
                if(!visited[num]){
                    q.offer(num);
                }
            }
        }
        
        return count;
    }

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

public class Main {

    public static void main(String[] args) throws IOException {
        int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
        boolean[] visited = new boolean[9];
        System.out.println(bfs(1, graph, visited));
    }

    static String bfs(int start, int[][] graph, boolean[] visited){
        StringBuilder sb = new StringBuilder();
        Queue<Integer> q = new LinkedList<>();

        q.offer(start);
        visited[start] = true;
        while(!q.isEmpty()){
            int nodeIndex = q.poll();
            sb.append(nodeIndex + " ->");
            for(int i = 0; i<graph[nodeIndex].length; i++){
                int temp = graph[nodeIndex][i];
                if(!visited[temp]){
                    visited[temp] = true;
                    q.offer(temp);
                }
            }
        }
        return sb.toString();
    }





}

 

5. 관련 문제

백준 1260

GitHub - Lee-Min-Jung/coding_test_practice

백준 1167

GitHub - Lee-Min-Jung/coding_test_practice

백준 2251

GitHub - Lee-Min-Jung/coding_test_practice

백준 1325

GitHub - Lee-Min-Jung/coding_test_practice

백준 18352

[Silver II] Title: 특정 거리의 도시 찾기, Time: 1236 ms, Memory: 278576 KB -Ba… · Lee-Min-Jung/coding_test_practice@

전력망을 둘로 나누기

게임맵 최단 거리

GitHub - Lee-Min-Jung/coding_test_practice

네트워크

퍼즐 조각 채우기