안녕하세요? 닉네임간편입니다.
저번 시간에는 그래프에 대해 알아보았습니다. 이번 시간에는 그래프를 이용한 탐색 알고리즘을 배워보겠습니다. 그래프의 탐색 알고리즘에서 가장 많이 사용되는 것에는 깊이 우선 탐색과 너비 우선 탐색이 있으며, 이번 시간에는 깊이 우선 탐색에 대해 알아보겠습니다.
1. 깊이 우선 탐색이란?
깊이 우선 탐색(Depth First Search)은 그래프의 모든 정점을 발견하는 방법 중 하나로, 이름 그대로 최대한 깊이 탐색한 이후 더 이상 탐색할 것이 없다면 그 이전으로 돌아가 탐색을 이어가는 것입니다.
위 그림을 예시로 설명하겠습니다. 현재 탐색을 정점 1에서부터 시작한다고 하겠습니다. 또한 인접한 간선이 여러 개일 경우 왼쪽을 먼저 탐색한다고 설정하겠습니다.
1) 1 -> 2
정점 1에 인접한 간선은 2로 향하는 간선과 5로 향하는 간선이며, 왼쪽을 먼저 탐색하므로 정점 2를 탐색합니다.
2) 2 -> 3
정점 2에서 인접한 간선은 두 개가 있습니다. 마찬가지로 왼쪽을 먼저 가므로 정점 3을 탐색합니다.
3) 2 <- 3
정점 3에서는 더 이상 다른 곳으로 연결된 간선이 없으므로 탐색이 종료됩니다. 따라서 정점 3을 탐색하기 직전 상태인 정점 2로 복귀합니다.
4) 2 -> 4
정점 2에서는 아직 탐색하지 않은 정점 4가 있습니다. 따라서 해당 방향의 간선을 따라가 정점 4를 탐색합니다.
5) 2 <- 4
정점 4에선 더 이상 다른 곳으로 연결된 간선이 없으므로 탐색을 종료합니다. 이후 정점 4를 탐색하기 직전 상태인 정점 2로 복귀합니다.
6) 1 <- 2
정점 2에서도 더 이상 탐색하지 않은 정점이 없습니다. 따라서 정점 2를 탐색하기 직전 상태인 정점 1로 복귀합니다.
7) 1 -> 5
정점 1에선 아직 탐색하지 않은 정점 5가 있습니다. 따라서 이 간선을 따라 정점 5를 탐색합니다.
8) 5 -> 6
정점 5에선 아직 탐색하지 않은 정점 6이 있습니다. 따라서 정점 6을 탐색합니다.
9) 1 <- 5 <- 6
정점 6에선 탐색하지 않은 정점이 없습니다. 따라서 직전 상태인 정점 5로 복귀합니다. 이때 정점 5도 더 이상 탐색하지 않은 정점이 없으므로 직전 상태인 정점 1로 복귀합니다.
10) 정점 1에서도 마찬가지로 탐색하지 않은 정점은 없습니다. 이때 정점 1이 최초로 탐색을 시작한 곳이므로, 모든 탐색을 종료합니다.
즉, 이 그래프의 경우 DFS를 적용한다면 번호 순서대로 정점을 탐색하게 됩니다. 이렇게 탐색을 하고 있는 분기에서 완벽하게 탐색을 한 이후 다른 분기를 탐색하는 방법을 깊이 우선 탐색이라고 합니다.
2. 깊이 우선 탐색의 구현
깊이 우선 탐색은 스택 혹은 재귀를 통해 구현합니다. 그러나 재귀 또한 함수가 호출될 때 스택 메모리에 계속해서 쌓이는 방식으로 호출되기 때문에, 이론적으론 스택과 동일한 원리로 사용된다고 보면 됩니다.
그러나 재귀 함수로 구현할 경우 탐색이 정상적으로 종료될 수 있도록 잘 조건을 잘 설정해야 합니다.
3. 깊이 우선 탐색의 시간 복잡도
깊이 우선 탐색의 시간 복잡도는 사용하는 그래프 표현 방식에 따라 나뉩니다.
1) 인접 행렬을 사용하는 경우
깊이 우선 탐색은 정점에 인접하는 간선 모두를 검사합니다. 따라서 이 경우 |V|개의 정점에 대해 |V|개의 간선을 모두 탐색하기 때문에 시간 복잡도는 O(|V|^2)가 됩니다.
2) 인접 리스트를 사용하는 경우
인접 리스트의 경우 간선의 개수는 |E|개이며, |V|개의 모든 정점에 대해서 탐색을 하면 총 |E|개의 간선에 대해 탐색하게 됩니다. 따라서 총 시간 복잡도는 O(|V|+|E|)가 됩니다.
4. 장점
1) 현재 탐색하고 있는 노드만 기억하면 되기 때문에 비교적 저장 공간에 대한 수요가 적습니다.
2) 찾고자 하는 노드가 깊이 있는 경우, 너비 우선 탐색 방식보다 해를 더 빨리 구할 수 있습니다. 그러나 언제나 그런 것은 아닙니다. 찾고자 하는 노드를 맨 마지막에 와서 찾을 수도 있기 때문입니다.
5. 단점
1) 만일 깊이가 무한할 경우 해를 찾을 수 없을 가능성이 있습니다.
만일 찾고자 하는 해가 5인데 1 -> 2 -> 3 -> 7 ->...로 가는 깊이가 무한할 경우 결코 해를 찾을 수 없게 됩니다. 따라서 특정 깊이까지 탐색을 제한하는 방식으로 이를 해결할 수 있습니다.
2) 해를 구하더라도 이것이 최적해(혹은 최단 경로 해)가 아닐 수 있습니다.
해가 여러 개 존재하더라도 해를 구하면 탐색이 종료되기 때문입니다. 따라서 최단 경로 해를 찾고자 한다면 너비 우선 탐색을 사용하거나, 깊이 우선 탐색으로 구한 해의 경로를 따로 저장한 다음 최적해를 구해야 합니다.
6. 예시
문제는 [백준] 11724번 연결 요소의 개수 문제입니다.
[문제 링크]
https://www.acmicpc.net/problem/11724
무방향 그래프에서 연결 요소의 개수를 구해야 합니다. 두 정점이 간선으로 연결되면 연결 요소가 되며, 예를 들어 1과 2가 연결되어있고 2와 3이 연결되어있다면 1,2,3은 연결 요소가 됩니다.
따라서 연결 요소의 개수를 구하기 위해선 모든 정점의 연결 여부를 탐색해야 하기 때문에 DFS를 적용해서 풀 수 있습니다.
a) 전체 코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
adj[a].append(b)
adj[b].append(a)
visited = [False] * (N + 1)
def dfs(now):
tmp = adj[now]
for n in tmp:
if not visited[n]:
visited[n] = True
dfs(n)
ans = 0
for i in range(1, N + 1):
if not visited[i]:
visited[i] = True
dfs(i)
ans += 1
print(ans)
이제 본격적으로 설명을 시작하겠습니다.
b) 재귀 설정
import sys
sys.setrecursionlimit(10 ** 6)
파이썬은 기본으로 최대 재귀 깊이가 1000으로 설정되어 있습니다. 따라서 이를 능가하는 재귀 깊이에 도달하기 위해선 setrecursionlimit() 메서드를 통해 늘려야 합니다. 만일 그러지 않는다면 RecursionError가 발생하게 됩니다.(제가 직접 경험한 일입니다...ㅎㅎ)
c) 인접 리스트 및 방문 여부 배열 생성
input = sys.stdin.readline
N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
adj[a].append(b)
adj[b].append(a)
visited = [False] * (N + 1)
adj라는 인접 리스트를 생성하고, 반복문을 통해 정점을 입력받습니다. 이때 무방향 그래프이기 때문에 a에서 b로 가는 간선이 있다면 b에서 a로 가는 간선도 있으므로 위처럼 둘 모두에 연결 여부를 입력해야 합니다.
또한 방문 여부를 확인하기 위한 visited 배열을 생성합니다.
d) dfs() 메서드 정의
def dfs(now):
tmp = adj[now]
for n in tmp:
if not visited[n]:
visited[n] = True
dfs(n)
now번 정점에 연결되어 있는 정점 목록을 tmp가 참조하도록 합니다.
이후 tmp에 존재하는 원소들에 대해서 아직 방문하지 않았다면, 방문 체크를 한 후 dfs() 메서드를 호출합니다. 이를 반복함으로써 최초로 dfs()를 호출한 정점의 연결 요소를 알 수 있으며, 해당 연결 요소를 모두 탐색할 수 있습니다.
e) 모든 정점 탐색 및 정답 출력
ans = 0
for i in range(1, N + 1):
if not visited[i]:
visited[i] = True
dfs(i)
ans += 1
print(ans)
모든 정점을 탐색해야 하므로 반복문을 통해 아직 탐색하지 않았다면 dfs() 메서드를 호출하도록 합니다. 이 메서드가 반환된다면 해당 요소의 연결 요소가 모두 탐색된 것이므로, 정답 개수 변수 ans에 1을 추가합니다.
이후 정답을 출력합니다.
f) 다른 풀이
이 문제는 인접 행렬을 사용해서 풀 수 있습니다. 논리는 앞선 풀이와 동일하니 전체 코드만 동봉하겠습니다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
adj = [[False] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
x, y = map(int, input().split())
adj[y][x] = adj[x][y] = True
visited = [False] * (N + 1)
ans = 0
def dfs(cur):
visited[cur] = True
for i in range(1, N + 1):
if adj[cur][i] and not visited[i]:
visited[i] = True
dfs(i)
for i in range(1, N + 1):
if not visited[i]:
dfs(i)
ans += 1
print(ans)
7. 마무리
이번 시간에는 깊이 우선 탐색에 대해 알아보았습니다. 다음 시간에는 너비 우선 탐색에 대해 알아보겠습니다.
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
[자료구조 with 코틀린] 1. LinkedList (0) | 2021.12.14 |
---|---|
[알고리즘 이론] 5. 너비 우선 탐색(BFS) (1) | 2021.09.03 |
[알고리즘 이론] 3. 그래프 (0) | 2021.08.28 |
[알고리즘 이론] 2. 그리디 알고리즘 (0) | 2021.08.27 |
[알고리즘 이론] 1. 브루트포스 알고리즘 (0) | 2021.08.26 |