DFS, BFS, 인접행렬, 인접리스트
#깊이우선탐색(DFS) #너비우선탐색(BFS) #인접행렬 #인접리스트
- 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식
인접행렬
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 0 | 7 | 5 |
| 1 | 7 | 0 | 무한 |
| 2 | 5 | 무한 | 0 |
1
2
3
4
5
6
7
8
9
10
11
12
# Python code
# 인접행렬
INF = 99999999
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
pring(graph) # -> [[0, 7, 5], [7, 0, 99999999], [5, 99999999, 0]]
인접 리스트
파이썬에서 인접 리스트를 이용해 그래프를 표현할 때는 단순히 2차원 리스트를 이용하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
# Python code
graph = [[] for _ in range(3)]
graph[0].append((1,7))
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))
print(graph) # -> [[(1,7), (2,5)], [(0,7)], [(0,5)]]
인접행렬 vs. 인접리스트
**메모리 측면: **인접행렬 ** 인접행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨. 반면에 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리가 효율적으로 사용됨.
**속도 측면: 인접행렬 > **인접리스트 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻기 위해 인접리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하므로 더 느림. 반면에 인접행렬 방식은 바로 접근이 가능함.
DFS, BFS
DFS(Depth-First Search)는 '깊이 우선 탐색'이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조에 기초하지만 실제로는 스택을 쓰지 않아도 구현이 된다. 바로 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. 그리고 DFS는 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Python code
# DFS 메서드 정의
def dfs(graph, v, visited):
#현재 노드를 방문 처리
visited[v] = True
print(v, end = ' ')
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
#각 노드가 연결된 정보를 인접리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 4],
[1, 7],
[1, 9],
[1, 5, 6],
[4, 6],
[4, 5],
[2, 8],
[7, 9, 10],
[3, 8, 11],
[8, 11],
[9, 10]
]
#각 노드가 방문된 정보를 (인접)리스트 자료형으로 표현(1차원 리스트). 0 ~ 11
visited = [False] * 12
# 정의된 DFS 함수 호출
dfs(graph, 1, visited) # -> 1 2 7 8 9 3 11 10 4 5 6
일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다. 기능상 차이는 없으나 코딩테스트에서는 관행적으로 낮은 번호 순으로 처리하는 편이라고 한다.
BFS(Breadth-First Search)는 '너비 우선 탐색'이라고도 부르며, 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. DFS가 최대한 멀리 있는 노드를 우선으로 탐색하는 것과는 반대이다. 보이는 가까운 것부터 청소하는 방식이 연상되는 것 같다.
BFS 구현은 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 또한 deque라이브러리를 사용하는 것이 좋으며 O(N)의 시간이 소요되고, 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이라고 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# Python code
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# 각 노드가 연결된 정보를 인접리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 4],
[1, 7],
[1, 9],
[1, 5, 6],
[4, 6],
[4, 5],
[2, 8],
[7, 9, 10],
[3, 8, 11],
[8, 11],
[9, 10]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트). 0 ~ 11
visited = [False] * 12
# 정의된 BFS 함수 호출
bfs(graph, 1, visited) # -> 1 2 3 4 7 9 5 6 8 11 10
참고)
그래프는 게임 맵과도 연관이 있다. 예를 들어 게임 맵이 4 x 4 형태의 2차원 배열이고 각 데이터를 좌표라고 생각해보자. 이 때 각 좌표를 상하좌우로만 이동할 수 있다면 다음과 같은 그래프의 형태로 바꿔서 생각할 수 있다.
| (1, 1) | (1, 2) | (1, 3) | (1, 4) |
|---|---|---|---|
| (2, 1) | (2, 2) | (2, 3) | (2, 4) |
| (3, 1) | (3, 2) | (3, 3) | (3, 4) |
| (4, 1) | (4, 2) | (4, 3) | (4, 4) |
이 글의 내용이 많은 도움이 된다면 아래 책을 사서 읽어보고 공부하는 것을 추천한다.
이것이 취업을 위한 코딩 테스트다 with 파이썬
1
2
3
4
5
6
저자
나동빈
출판
한빛미디어
발매
2020.08.05.