10 / 14강

그래프와 탐색

친구 관계나 지하철 노선은 부모와 자식의 계층으로만 나뉘지 않습니다. 여러 곳이 서로 연결되고, 한 바퀴 돌아 같은 곳으로 올 수도 있습니다. 이런 관계를 그래프로 나타냅니다.

• 정점(vertex): 사람이나 역처럼 연결의 대상입니다.
• 간선(edge): 정점 사이의 연결입니다. 방향이 있으면 방향 그래프입니다.
• 가중치(weight): 이동 시간처럼 간선에 붙인 비용입니다.

연결을 저장하는 두 방법

인접 리스트는 정점마다 이웃 목록을 둡니다. 정점 수가 V, 간선 수가 E라면 공간은 O(V+E)입니다. 인접 행렬은 두 정점의 연결 여부를 표의 한 칸에 저장하며 O(V²) 공간을 씁니다. 행렬은 특정 연결을 바로 확인하기 좋지만 연결이 적어도 표 전체가 필요합니다.

BFS는 가까운 곳부터

너비 우선 탐색(BFS)은 큐를 씁니다. 시작점의 이웃, 그 이웃의 이웃 순서로 범위를 넓힙니다. 아래 예제는 양방향 연결을 양쪽 목록에 모두 적었습니다.

from collections import deque

graph = {
    "A": ["B", "C"], "B": ["A", "D"],
    "C": ["A", "D"], "D": ["B", "C"]
}
queue = deque(["A"])
seen = {"A"}

while queue:
    node = queue.popleft()
    print(node)
    for neighbor in graph[node]:
        if neighbor not in seen:
            seen.add(neighbor)
            queue.append(neighbor)

출력은 A B C D 순서입니다. D는 B와 C 양쪽에서 발견되지만 큐에 넣을 때 방문 표시를 하므로 한 번만 넣습니다. 순서는 이웃을 나열한 순서에 따라 달라질 수 있습니다.

DFS는 깊이 들어갔다 돌아오기

깊이 우선 탐색(DFS)은 한쪽으로 갈 수 있을 때까지 간 뒤 되돌아옵니다. 스택이나 재귀로 구현합니다. 같은 그래프에서 B를 먼저 고르면 A B D C처럼 방문할 수 있습니다.

인접 리스트를 쓰고 방문 확인을 평균 O(1)로 처리하면 BFS와 DFS는 O(V+E)입니다. 한 시작점에서 탐색하면 도달 가능한 정점만 방문합니다. 그래프 전체를 보려면 아직 방문하지 않은 정점에서 다시 시작해야 합니다.

확인 문제

방문 표시를 하지 않으면 무슨 문제가 생길까요? BFS가 구하는 최단 경로는 어떤 비용을 기준으로 할까요?