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

Algorithm

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

비번변경 2024. 5. 29. 23:37

너비 우선 탐색

너비 우선 탐색(Breadth First Search)이란 그래프 탐색 방법 중 하나로, 임의의 시작 정점을 방문한 후 인접한 모든 정점을 우선 방문하는 방법이다. 갈림길에 연결되어 있는 모든 길을 탐색한 뒤, 다시 연결되어 있는 모든 길을 넓게 탐색하는 방법이다.

그래프 내 모든 간선의 가중치가 같으면 너비 우선 탐색으로 찾아낸 두 점 사이의 경로는 최단 경로에 해당한다. 따라서 두 점 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 너비 우선 탐색을 사용한다.

보통 너비 우선 탐색에 대해 찾아보면 트리 형태의 그래프 탐색이 가장 흔하게 보이는데, 트리 형태가 아닌 그래프에도 사용할 수 있다. 또는 미로 찾기와 같은 이차원 배열에도 사용할 수 있다.

동작 방식

너비 우선 탐색은 방문한 노드의 인접한 노드를 기억해두었다가 각 노드의 인접한 노드를 다시 기억해두어야 한다. 따라서 일반적으로 큐(Queue)와 반복문을 사용한 형태로 구현하게 된다.

아래 그림은 너비 우선 탐색 과정을 나타낸 것이다.

시작 정점인 a를 방문한다.
- 큐에 a를 방문한 정점으로 추가한다.
- a의 방문 여부를 갱신한다.
큐 내 데이터를 모두 소진할 때까지 아래 과정을 반복한다.
- 큐에서 방문했던 정점을 꺼낸다.
- 방문했던 정점에서 인접한 정점 중 방문하지 않은 정점을 큐에 추가한다.
- 방문할 정점의 방문 여부를 갱신한다.

구현 코드

너비 우선 탐색을 Python으로 구현한 코드는 다음과 같다.

# 일반적으로 그래프는 딕셔너리로 표현한다. key는 정점, value는 인접한 정점을 가리킨다.
def bfs(graph: dict, start):
    # 방문 배열. visited[node] = True이면 node는 방문한 상태이다.
    visited = {i: False for i in graph.keys()}

    # 시작 정점 방문
    queue = [start]
    visited[start] = True

    # 큐가 빌 때까지 반복
    while queue:  # 큐가 빌 때까지 반복
        current = queue.pop(0)
        
        for nxt in graph[current]:
            # 인접 정점이 방문하지 않았다면
            if not visited[nxt]:
                # 정점 방문
                queue.append(nxt)
                visited[nxt] = True

보통 최단 거리와 경로를 구하는 경우가 많으므로 방문 정점까지의 거리, 어느 정점에서 왔는지 정도의 정보를 함께 처리하는 것이 좋다.