BFS

Breadth First Search

너비 우선 탐색

가까운 노드부터 탐색하는 알고리즘

큐 자료구로를 사용하는 것이 정석

(인접한 노드를 큐에 넣으면 먼저 들어온 것이 먼저 나가게 되므로 가까운 노드부터 탐색할 수 있다)

 

사용하는 경우 (유형)

연결된 그래프를 탐색하는 경우

최단 거리(최소 횟수)를 구하는 경우 (현재 노드에서 가까운 곳을 먼저 찾기 때문)

그래프의 규모가 크지 않고 시작 지점으로부터 대상이 멀지 않은 경우

cf) 경로의 특징을 저장하는 경우에는 DFS 사용 (BFS는 경로의 특징을 가질 수 없다)

 

동작 방식

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 2번을 더 이상 수행할 수 없을 때까지 반복

 

code 

# 스택을 사용하기에 
# deque 라이브러리를 사용하는 것이 좋다 
from collections import deque

def bfs(graph, start, visited):
    # 큐 생성 
    queue = deque([start])
    # 방문 처리 
    visited[start] = True

    # 큐에 값이 있다면 
    while queue:
        # 가장 먼저 들어온 노드 출력 
        v = queue.popleft()
        print(v, end = ' ')
        # 인접한 노드 모두 방문 
        for i in graph[v]:
            # 방문하지 않은 노드라면 
            if not visited[i]:
                # 큐에 추가
                queue.append(i)
                # 방문처리 
                visited[i] = True

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

 

예제

1260번: DFS와 BFS

1260번: DFS와 BFS

2178번: 미로 탐색

2178번: 미로 탐색