[파이썬] 너비 우선 탐색 (BFS)의 구현과 활용

01 Sep 2023

python

너비 우선 탐색(BFS)은 그래프를 탐색하는 알고리즘 중 하나로, 정점들을 탐색하는 순서에 너비를 우선으로 한다는 특징을 가지고 있습니다. 이러한 특징 때문에 BFS는 최단 경로를 찾거나, 그래프의 구조를 분석하는 등의 다양한 문제에 활용됩니다.

BFS 알고리즘의 구현

BFS 알고리즘은 큐(Queue) 자료구조를 사용하여 구현할 수 있습니다. 다음은 Python으로 BFS 알고리즘을 구현한 예제 코드입니다.

from collections import deque

def bfs(graph, start):
    visited = set()   # 방문한 정점을 저장하는 set 자료구조
    queue = deque()   # 큐 자료구조
    queue.append(start)   # 시작 정점을 큐에 추가
    
    while queue:
        vertex = queue.popleft()   # 큐에서 정점을 하나 꺼냄
        
        if vertex not in visited:   # 정점이 방문된 적이 없으면
            visited.add(vertex)   # 정점을 방문 처리
            
            for neighbor in graph[vertex]:   # 현재 정점에 연결된 인접 정점들에 대해
                if neighbor not in visited:   # 방문되지 않은 정점이라면
                    queue.append(neighbor)   # 큐에 추가

위의 코드에서 graph는 그래프를 나타내는 자료구조로, 인접 리스트 형태로 구현되어야 합니다. start는 탐색을 시작할 정점을 의미합니다.

BFS의 활용

BFS는 최단 경로 문제를 해결하는데 사용될 수 있습니다. 시작 정점에서부터 다른 모든 정점까지의 최단 경로를 찾을 수 있습니다.

또한 BFS는 그래프의 구조를 분석하는 데에도 유용합니다. 그래프의 연결 여부를 확인하거나, 그래프의 연결 요소들을 찾는 등의 작업을 수행할 수 있습니다.

아래는 BFS 알고리즘의 활용 예시 중 하나인 최단 경로 탐색 문제를 풀기 위한 코드입니다.

from collections import deque

def shortest_path(graph, start, end):
    visited = set()
    queue = deque()
    queue.append((start, [start]))   # 시작 정점과 해당 경로를 큐에 추가
    
    while queue:
        vertex, path = queue.popleft()
        
        if vertex == end:   # 목표 정점에 도착한 경우 경로 반환
            return path
        
        if vertex not in visited:
            visited.add(vertex)
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append((neighbor, path + [neighbor]))   # 새로운 경로를 생성하여 큐에 추가
                    
    return None   # 탐색 실패 시 None 반환

위의 코드에서 graph는 그래프를 나타내는 자료구조, start와 end는 경로를 찾고자 하는 출발 정점과 도착 정점을 의미합니다. 코드가 실행되면 시작 정점에서 도착 정점까지의 최단 경로를 반환하게 됩니다.

BFS 알고리즘은 다양한 문제에 활용될 수 있는 강력한 탐색 알고리즘이며, 위의 예제 코드를 참고하여 실제로 적용해볼 수 있습니다. 해결하고자하는 문제에 따라 BFS를 적절히 응용하여 문제를 해결해보세요.