IT-garden

너비 우선 탐색(BFS : Breadth First Search)은 시작점으로부터 가까운 점을 먼저 방문하고 멀리 떨어져 있는 점을 나중에 방문하는 탐색 방법입니다.

특징은 시작점으로부터 거리가 가까운 점의 순서로 탐색이 진행됩니다.

거리의 의미는 시작점으로부터 어느 점까지의 경로 중 가장 짧은 경로의 길이를 의미합니다.

즉, 거리가 a인 점들을 모두 방문하고 거리가 a + 1인 점들을 모두 방문합니다.

너비 우선 탐색은 크게 2가지 문제에서 자주 사용됩니다.

1. 그래프를 모두 탐색하는 문제

2. 특정 그래프에서 가중치가 모두 같을 때 최단거리를 찾는 문제

너비 우선 탐색의 방법은

1. 큐에서 하나를 꺼내 제거하고(제거 하는 것이 방문한 점)

2. 해당 점과 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

너비 우선 탐색에서는 큐를 사용합니다.

큐는 방문한 점들을 저장하고 제거하는데 사용하고 큐가 공백이 될 때까지 탐색이 계속됩니다.

위와 같은 그래프가 있다고 가정하고 너비 우선 탐색을 실시해보겠습니다.

시작점은 1로 생각하고 모든 그래프를 탐색하려고 합니다.

점을 방문할때는 더 작은 순서로 방문하도록 하겠습니다.

기존 그래프에서 1을 큐에 넣어줍니다. 1이 시작점이기 때문입니다.

그리고 1을 방문하여 큐에서 1을 제거하고 1과 연결되어 있는 점들 중 방문하지 않은 점인 2와 3을 큐에 넣습니다.

큐에서 다음으로 2를 방문하여 큐에서 2를 제거하고 2와 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

여기서 1은 이미 방문했기 때문에 큐에 넣지 않고 4와 5를 넣습니다.

다음으로 3를 방문하여 큐에서 3를 제거하고 3와 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

여기서 1은 이미 방문했기 때문에 6만 큐에 넣습니다.

큐에서 4를 방문하며 4를 제거합니다. 이때 4에 연결된 점들 중 방문하지 않은 점이 없기 때문에 큐에 값을 넣어주지 않습니다.

마찬가지로 5도 방문하고 큐에서 제거해줍니다.

마지막으로 6도 방문하고 큐에서 제거해줍니다.

그럼 모든 점들의 방문이 끝나 탐색이 종료됩니다.

위의 그래프에서 너비 우선 탐색의 방문 순서는 1 → 2 → 3 → 4 → 5→ 6 입니다.

큐를 이용한 너비 우선 탐색의 파이썬 코드입니다.

import queue

n = 6 # 정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 # 시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a = [[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def bfs(start):
    q = queue.Queue()
    q.put(start)
    ch[start] = 1

    while not q.empty():
        now = q.get()
        print(now, end=' ')
        for i in a[now]:
            if ch[i] != 1:
                ch[i] = 1
                q.put(i)
                
bfs(v)

# 최종 출력>>1 2 3 4 5 6

덱을 이용한 너비 우선 탐색의 파이썬 코드입니다.

from collections import deque

n = 6 #정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 #시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a=[[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def bfs(start):
    de = deque()
    de.append(start)
    ch[start] = 1 

    while len(de) != 0:
        now = de.popleft()
        print(now, end=' ')
        for i in a[now]:
            if ch[i] != 1:
                ch[i] = 1
                de.append(i)
                
bfs(v)

# 최종 출력>>1 2 3 4 5 6