본문으로 건너뛰기
실습하기

너비 우선 탐색(BFS) 구현 방법

1. 큐 사용​

  • BFS는 큐를 사용하여 탐색할 노드들을 관리합니다. 큐를 사용하여 각 레벨별로 노드를 순차적으로 탐색합니다.
큐 사용 예시
def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            # 리스트를 이용하여 중복 제거
            queue.extend([n for n in graph[node] if n not in visited])

    return visited

2. 레벨별 탐색​

  • BFS는 각 노드의 레벨별로 인접 노드를 탐색합니다. 이는 큐의 선입선출(FIFO) 특성을 활용합니다.
레벨별 탐색 예시
while queue:
    node = queue.pop(0)
    if node not in visited:
        visited.append(node)
        # 리스트를 이용하여 중복 제거
        queue.extend([n for n in graph[node] if n not in visited])

시간 복잡도​

  1. 시간 복잡도: (O(V + E))

    • 여기서 V는 정점의 수, E는 간선의 수를 나타냅니다. 각 정점은 한 번씩 방문되며, 각 간선은 한 번씩 검사됩니다.

  2. 최단 경로 탐색: BFS는 무방향 그래프에서 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 효과적입니다.

  3. 넓은 범위 탐색: BFS는 레벨별 탐색을 통해 넓은 범위의 노드들을 효과적으로 탐색할 수 있습니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!