[파이썬(Python)]DFS/BFS

나동빈 님의 이것이 취업을 위한 코딩 테스트다 with 파이썬을 학습 목적으로 정리한 글입니다.

 

DFS(Depth-First Search)

그래프에서 깊은 부분을 우선적으로 탐색하는 깊이 우선 탐색 알고리즘입니다.

그래프

그래프는 노드(Node)/정점(Vertex)와 간선(Edge)으로 구성됩니다. 간선은 두 노드를 잇는 선인데, 이때 '두 노드는 인접하다'라고 합니다. 그래프는 두가지 방식으로 표현합니다.

인접 행렬(Adjacency Matrix)

INF = 999999999

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
     [7, 0, INF],
     [5, INF, 0]
]

print(graph)

 

2차원 배열로 연결 관계를 표현합니다.
연결되지 않은 노드 간에는 무한(Infinity)의 비용이라고 표현하며, 이를 INF라는 상수에 담아 사용합니다.

그래프 해석에는 영향을 주지 않도록 999999999 처럼 매우 큰 값을 할당합니다.

인접 리스트(Adjacency List)

# 행이 3개인 2차원 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append(1, 7)
graph[0].append(2, 5)

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append(0, 7)

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append(0, 5)

print(graph)

• 리스트로 연결 관계를 표현합니다.
• 인접 행렬 방식은 인접하지 않은 노드까지 모두 저장하므로 인접 리스트 방식에 비해 메모리 사용량이 큽니다.
• 특정 노드가 다른 노드와 연결되어 있는지 확인하려면, 인접 행렬 방식은 인덱스를 통해 곧바로 할 수 있는 반면, 인접 리스트 방식은 리스트의 요소를 모두 탐색해야 하는 단점이 있습니다.
• 반드시 특정한 노드와 인접한 모든 노드를 순회해야 하는 경우라면, 연결 리스트 방식이 공간을 더 효율적으로 사용할 수 있는 방식입니다.

DFS 동작 과정

1. 탐색 시작 노드 스택에 삽입하고 방문 처리 합니다.
2. 스택의 최상단 노드에 인접한 노드 중 방문하지 않은 노드가 있으면 해당 노드를 스택에 넣고 방문 처리 합니다. 모든 인접 노드에 방문했으면 스택에서 최상단 노드를 꺼냅니다.
3. 2번을 더 이상 할 수 없을 때까지 반복합니다.

---

BFS(Breadth First Search)

• 최대한 멀리 있는 노드를 우선적으로 탐색하는 DFS와 달리 가까운 노드부터 탐색하는 알고리즘입니다.
• 보통 큐 자료구조를 이용해서 BFS를 구현합니다. 인접한 노드를 반복적으로 큐에 넣습니다.

BFS 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리합니다.
2. 큐에서 노드를 꺼내고 그 노드의 인접 노드 중 방문하지 않는 노드를 전부 큐에 삽입합니다.
3. 2번을 더 이상 수행이 불가할 때까지 반복 수행합니다.

해당 알고리즘은 deque 라이브러리를 이용해서 구현하는 것이 좋습니다. 시간복잡도는 O(N)이며, 일반적으로 DFS보다 탐색 시간이 짧은 편입니다.