[자료구조 및 알고리즘] BFS (Breadth First Search, 너비우선탐색)

BFS (너비우선탐색)

 

시작노드에서 시작한 뒤 다음 깊이로 진행하기 전 출발점에서 발생한 모든 분기를 탐색한 후, 다음 레벨로 진입한다. 갈림길의 모든 지점들을 탐색한 뒤 갈림길에서 발생한 모든 갈림길을 다시 순차적으로 탐색하는 모습이 가로로 훑는 모양새이다.

 

DFS의 경우 무한루프나 스택오버플로의 우려가 있었지만, BFS의 경우 모든 경로에 대해 동시에 탐색을 진행하므로 그럴 걱정은 없다.

 

BFS의 특성

 

1. BFS는 재귀로 구현할 수 없다.

2. 가중치가 없는 그래프에서 두 노드 사이의 최단경로나 임의의 경로를 구하는 데 사용한다. 

3. DFS보다 검색에서 유리하다. (DFS는 조건을 만족하는 순회에 초점)

4. 방문한 노드들을 저장한 후 차례대로 꺼내는 FIFO (선입선출) 방식으로 탐색을 진행하기에 큐를 사용한다.

 

BFS의 장점

 

1. 해가 여러 개더라도 가장 먼저 구한 해가 최단경로임을 보장한다.

2. 최단경로가 존재한다면 특정 경로의 길이가 무한이더라도 최단경로를 찾을 수 있다.

 

BFS의 단점

 

1. 노드의 개수가 많아지면 효율성이 떨어진다.

2. DFS는 재귀호출로 발생한 중간값만을 스택에 저장하지만, BFS는 큐에 탐색할 노드들을 저장하므로 저장공간을 많이 요구한다.

 

코드

 

import sys
from collections import deque
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n,m,r = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def bfs(v):
    queue = deque([v])
    path = []
    while queue:
        k = queue.popleft()
        if k not in path:
            path.append(k)
            graph[k].sort()
            for i in graph[k]:
                queue.append(i)
    return path

print(*bfs(r))