🧬[너비우선탐색 알고리즘]

강_토발즈 2024. 12. 20. 00:55

깊이우선탐색 알고리즘은 그래프나 트리형태의 자료구조를 탐색하는 알고리즘이었고, 특정 노드를 시작하여 노드의 연결된 끝 까지 탐색하고 나오는 알고리즘 이었다.
이와 다르게 너비우선탐색 알고리즘은 그 이름처럼 특정 노드에서 시작하여 인접한 노드를 먼저 탐색하고, 그 인접노드의 인접노드를 탐색하는 방식으로 진행된다. 따라서 최단경로를 찾거나 레벨 단위로 노드를 탐색할 때 유용(시간이 덜 걸린다) 하다.

-> 최단 경로를 찾는 방법은 트리 형태로 경우의 수가 가지 형태로 뻗어 나갈텐데, 레벨이 가장 먼저 끝나는 노드를 만나면 탐색이 종료되니까 유용한 게 맞는 것 같다!!

1. 너비우선탐색 알고리즘의 개념

탐색 방식 : 큐 자료구조를 사용하여 구현한다. 시작 노드를 큐에 추가하고, 큐에서 노드를 꺼내면서 그 노드의 인접 노드를 큐에 추가
탐색 순서 : 먼저 큐에 들어간 노드가 먼저 처리되므로, 레벨 단위로 탐색이 이루어진다.

2. 알고리즘의 작동방식

시작 노드를 큐에 추가하고 방문 표시( 방문한 노드만 있는 자료구조를 생성해서 저장하면 됨)
큐가 비어있지 않는 동안 ( while 문으로 구현)
- 큐에서 노드를 꺼낸다
-그 노드의 모든 인접 노드를 확인한다.
-방문하지 않은 인접 노드를 큐에 추가하고 방문 표시(자료구조에 저장)
탐색이 완료될 때 까지(큐가 빌 때 까지) 반복한다.

3. 시간복잡도

O (A + B) A 는 노드의 수 B 는 간선의 수

4.파이썬 구현방법

from collections import deque

def bfs(graph, start):
    # 큐 초기화
    queue = deque([start])
    visited = set([start])  # 방문한 노드 집합

    while queue:
        # 큐에서 노드 꺼내기
        vertex = queue.popleft()
        print(vertex, end=' ')  # 현재 노드 출력

        # 인접 노드 탐색
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)  # 방문 표시
                queue.append(neighbor)  # 큐에 추가
                
# 그래프 예시 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# BFS 실행
bfs(graph, 'A')

# 출력 결과 = A B C D E F

코드의 이해를 위해 노가다를 시작한다

1. A 부터 노드가 시각되므로 저장하고, 출력한 다음에 꺼낸다

큐 : A

방문 확인 자료구조 : A

출력 A

큐 :

방문 확인 자료구조 : A

2.graph 에서 A가 인접한 노드를 발견하여 큐와 방문 자료구조에 추가한다.(방문 하지 않은 노드)

A : [B, C] 와 인접해 있으므로

큐 : B C

방문 확인 자료구조 : B A C

--- while 문 한 번 반복 완료 ---

큐 : B C

방문 확인 자료구조 : B A C

2-1. 큐 자료구조가 비어있지 않으므로 while 문 실행. 큐에서 노드를 꺼내고 출력한다

출력 A B ( B 가 추가)

큐 : C

방문 확인 자료구조 : B A C

2-2. graph 에서 B 가 인접한 자료구조를 큐와 방문 자료구조에 추가한다 (방문 하지 않은 노드)

-> B : [A, D, E] (A는 방문한 적 있음, D, E 는 방문한 적 없음)

큐 : C D E

방문 확인 자료구조 : A C B D E

--- while 문 두 번 반복 완료

큐 : C D E

방문 확인 자료구조 : A C B D E

3-1. 큐 자료구조가 비어있지 않으므로 while 문 실행, 큐에서 노드를 꺼내고 출력한다.

출력 A B C

큐 : D E

방문 확인 자료구조 : A C B D E

3-2. graph 에서 C 가 인접한 자료구조를 큐와 방문 자료구조에 추가한다 (방문 하지 않은 노드)

-> C : [A, F] (A 는 방문한 적 있고, F는 방문한 적 없다)

큐 : D E F

방문 확인 자료구조 : A F C B D E

--- while 문 세번 반복 완료 ---

이제부터는 방문 확인 자료구조에 모든 노드가 있으니 큐와 방문 자료구조에 추가하는 구문을 실행되지 않을 것 이고,

큐에 들어있는 순서대로 D E F 가 출력되면서 결과로 A B C D E F 가 출력 될 것이다.

마무리

코드를 하나하나 디버깅 모드로 실행하고, 자료구조에 어떻게 결과들이 저장되는지 보면서 로직이 제대로 실행되는지 확인하니까 해당 알고리즘에 믿음이 간다.
하지만 어떻게 생각해서 이 알고리즘을 만들어낸건지는 100% 이해하지 못했다. 하지만 새로운 알고리즘을 개발해 내는것은 지금 실력으로선 무리이고, 이미 개발되어 있는 알고리즘들을 내 것으로 만들어서 유용하게 사용하는게 우선이라고 생각했다!

현재까지 정리한 유클리드 호제법, 깊이우선탐색, 아리스토네네스의 체, 너비우선탐색 알고리즘들에 대해 자체 중간고사를 실시하여 알고리즘을 강제로 체득(?) 하는 시간을 갖도록 해야겠다.