[DS&AL] 깊이 우선 탐색 (DFS, Depth-First Search) 정리
너비 우선 탐색 (BFS)에 대해 이해하려면, 먼저 그래프 탐색이 무엇인지를 알아야 합니다.
그래프 탐색
그래프 탐색 문제 (Graph Search)는 어떤 한 그래프와 해당 그래프의 시작 정점(Node, Vertex)이 주어졌을 때, 시작점에서 간선(Edge)를 타고 이동할 수 있는 모든 정점들을 찾아야 하는 문제를 말합니다. 이 그래프 탐색 문제의 대표적인 예시로는,
- DFS (Depth-First Search, DFS)
- BFS (Breath-First Search, BFS) 가 있습니다.
이전에 다룬 BFS에 이어, 이번에는 대표적인 DFS에 대해 다루겠습니다.
DFS (깊이 우선 탐색)
DFS (깊이 우선 탐색)은 그래프 탐색 알고리즘의 큰 유형 중 하나로서, 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘입니다. 즉, 한 지점에서 루트 노드(혹은 임의의 다른 노드)에서 시작해 다음 분기로 넘어가기 전, 해당 분기를 완벽하게 탐색하는 방법입니다. 쉽게 말씀드리면, 일단 끝까지 가본다 -> 만약 끝까지 갔는데, 막히면 되돌아간다. 이런 느낌으로 이해하시면 될 것 같습니다.
DFS 작동원리는 크게 다음과 같습니다.
- 탐색 시작 노드 정보를 스택 등의 방법을 사용하여 방문처리를 진행한다.
- 방문처리 : 탐색된 노드를 재방문하지 않도록 구분하는 형식
- 현재 노드에서 방문하지 않은 인접 노드가 존재한다면, 해당 노드로 이동해 다시 위 과정을 반복한다. (보통 DFS에서는 재귀 형식으로 진행합니다.)
- 더 이상 방문할 수 있는 인접 노드가 없다면, 이전 노드로 되돌아가는 Backtracking(백트래킹)을 수행한다.
- 위의 과정을 모든 노드를 방문할 때까지 반복한다.
그림으로 설명드리면 다음과 같습니다.
그림에서 DFS의 작동 원리를 확인하면 크게 다음과 같이 진행됩니다.
- 시작 노드인 노드 0을 큐에 삽입하고 방문처리한다.
- 0에서 먼저 이어지는 노드 1을 방문하고, 방문처리를 진행한다. 그 다음, 노드 1을 기준으로 재귀 or 스택 탐색을 진행한다.
- 노드 7까지 순차적으로 반복 탐색을 진행하고, 방문하지 않은 노드가 없을 경우, 백트래킹을 적용하여 노드 1로 되돌아온 다음, 노드 4를 탐색한다.
- 노드 4를 탐색한 이후, 0으로 백트래킹한 다음, 탐색하지 않은 노드 2에서도 같은 과정을 반복한다.
- 이 과정을 계속 진행해서 마지막 9까지 방문한다. 이렇게 진행되면, 방문 순서는 0 -> 1 -> 3 -> 7 -> 4 -> 2 -> 5 -> 6 -> 8 -> 10 -> 9의 순서대로 방문합니다.
Backtracking
DFS에 빠질 수 없는 개념이 바로 백트래킹입니다. 백트래킹은, 답을 찾아가는 과정에서 답이 아니게 되어 막히게 될 때, 이전 단계로 되돌아가서 다시 답을 찾는 방법입니다.
DFS에서 크개 백트래킹이 발생하는 케이스는 3가지가 있습니다.
- 더 이상 방문할 인접 노드가 없는 경우
- 현재 경로가 주어진 조건을 만족하지 못하는 경우
- 정답이 될 수 없다고 판단되는 경우
이 3가지 조건 중 하나에 해당되는 경우, 이전 노드로 돌아가 다른 경로를 탐색해야 합니다. DFS에서는 주로 재귀를 사용(스택구조)해서 이러한 백트래킹이 발생합니다.
그래서 DFS와 백트래킹은 한묶음이라고 생각하는 것이 좋습니다. DFS는 크게 재귀형식으로 코드를 작성하기 때문에, 이러한 재귀 방법에 백트래킹이 들어가기 때문이죠.
DFS 구현
DFS의 구현에는 스택(Stack) 자료구조를 사용합니다. (파이썬 기준으로 말씀을 드리면, 재귀 함수를 사용하면 내부적으로 스택을 사용하게 됩니다.)
- Stack은 LIFO(Last In, First Out) 방법입니다.
DFS에서 방문처리를 할때, BFS와는 다르게, 큐를 잘 사용하지 않고, 방문했는지 아닌지 여부만 간단하게 확인합니다.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set()
다음 코드와 같이 방문한 순서대로 표시하는 set()으로 하거나, 방문 순서를 고려하지 않는다면 그래프의 정보만큼 False가 담긴 리스트를 만든 후, 방문한 노드마다 True로 바꿔주는 형식으로 진행할 수 있습니다.
visited = [False] * n
# 방문했을 때, 다음과 같이 변환
visited[v] = True
기본적인 DFS 코드는 다음과 같습니다.
def dfs(curr_node, graph, visited):
visited.add(curr_node)
for next_node in graph[curr_node]:
if next_node not in visited:
dfs(next_node, graph, visited)
return visited
def solution():
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set()
dfs('A', graph, visited)
return visited
코드에 대한 설명을 드리면, 이 코드는 재귀 호출을 이용한 DFS의 기본 형태입니다. 여기서 curr_node는 현재 탐색중인 노드, graph는 인접 리스트 형태로 표현된 그래프, visited는 방문한 노드의 정보를 저장합니다.
dfs함수를 실행했을 때,
- 현재 탐색중인 노드를 방문처리합니다.
- 현재 노드와 직접 연결된 모든 노드를 하나씩 확인합니다. -> DFS는 순서대로 하나씩 닿는 데까지 탐색합니다.
- 아직 방문하지 않은 노드일 때, 해당 노드로 이동하여 다시 DFS를 수행하도록 재귀 호출을 수행합니다.
- 더 이상 이동할 수 없는 경우, 함수 호출이 종료되고 자동으로 이전 노드로 돌아가는 백트래킹 과정이 수행됩니다.
- 모든 탐색이 종료된 후, 방문한 노드들의 집합을 반환하며, 이 경우, set을 사용했기 때문에 순서는 확인할 수 없습니다.
- 만약 순서를 확인하고자 한다면, 리스트로 변경하면 됩니다.
이렇게 수행한 DFS의 시간 복잡도는 \(O(V+E)\)입니다. (정점 수 + 엣지 수)
DFS의 문제 유형
DFS의 문제 유형은 크게 다음과 같이 나눌 수 있습니다.
1. 경로 찾기
DFS에서 경로 찾기 문제는 시작점에서 목표점까지 도달할 수 있는지를 주로 확인하는 문제입니다. 혹은, 어떤 경로로 가야 하는지를 묻는 유형입니다. 이러한 문제에서는 갈 수 있는 길이 존재하는지만 묻는 경우도 있고, 경로를 하나 출력하라고 할 수 있습니다. 또한, 갈 수 있는 모든 경로를 세는 문제가 등장할 수 있습니다.
# 그래프 s에서 t까지 도달가능한지 확인하는 문제
def dfs_path_exists(graph, s, t):
visited = set()
def dfs(u):
if u == t:
return True
visited.add(u)
for v in graph.get(u, []):
if v not in visited:
if dfs(v):
return True
return False
return dfs(s)
# 사용 예시
graph = {1:[2,3], 2:[4], 3:[], 4:[]}
print(dfs_path_exists(graph, 1, 4)) # True
print(dfs_path_exists(graph, 3, 4)) # False
2. 연결 요소 문제
연결 요소 문제는 현재 노드를 기준으로 연결된 모든 노드를 탐색하는 문제입니다. 이 문제에서는 그래프에서 서로 연결된 컴포넌트 (분리된 그래프)가 몇개인지를 구하는 문제가 주를 이룹니다.
“연결되어 있다”라는 정의가 문제에서 주어지는데, 간선으로 이어지는지, 상하좌우로 인접한지 등 조건이 주로 제시됩니다.
이러한 케이스에서는, DFS를 한 번 돌리면, 그 노드가 속한 덩어리를 전부 방문처리하는 경우가 있어, 간단하게 말하면, DFS 시작 횟수가 정답이 되는 경우가 존재합니다.
# 무방향 그래프(Undirected graph)에서 연결 요소 개수 확인하기
def count_components(graph, n):
visited = [False] * (n + 1)
def dfs(u):
visited[u] = True
for v in graph.get(u, []):
if not visited[v]:
dfs(v)
cnt = 0
for i in range(1, n + 1):
if not visited[i]:
dfs(i)
cnt += 1
return cnt
# 사용 예시 (1-2-3 연결, 4-5 연결, 6 혼자)
graph = {1:[2], 2:[1,3], 3:[2], 4:[5], 5:[4], 6:[]}
print(count_components(graph, 6)) # 3
3. 플러드 필
플러드 필 문제, 일명 땅따먹기 문제는 그래프의 영역을 특정 색상으로 채우는 문제입니다. 여기서는 주로 같은 조건으로 이어진 영역을 전부 방문, 즉 칠하는 문제입니다. (예를 들어 1을 0으로 바꾸는 경우)
# 예시 : 1로 연결된 영역을 2로 칠하는 문제
def flood_fill(board, sy, sx, target=1, paint=2):
n, m = len(board), len(board[0])
def dfs(y, x):
board[y][x] = paint
for dy, dx in [(-1,0),(1,0),(0,-1),(0,1)]:
ny, nx = y + dy, x + dx
if 0 <= ny < n and 0 <= nx < m and board[ny][nx] == target:
dfs(ny, nx)
if board[sy][sx] == target:
dfs(sy, sx)
# 사용 예시
board = [
[1,1,0],
[1,0,0],
[0,1,1],
]
flood_fill(board, 0, 0, target=1, paint=2)
print(board)
# [[2,2,0],[2,0,0],[0,1,1]]
플러드필의 다른 예시는 다음과 같습니다.
def dfs(row, col, graph, old_color, new_color):
# 이동 조건을 old_color로 검사
if 0 <= row < len(graph) and 0 <= col < len(graph[0]):
if graph[row][col] == old_color:
graph[row][col] = new_color
dfs(row - 1, col, graph, old_color, new_color)
dfs(row + 1, col, graph, old_color, new_color)
dfs(row, col - 1, graph, old_color, new_color)
dfs(row, col + 1, graph, old_color, new_color)
def solution(sr, sc, graph):
new_color = 0
visited = set()
# 응용 포인트1: 모든 영역 탐색
for row in range(len(graph)):
for col in range(len(graph[0])):
if (row, col) not in visited:
visited.add((row, col))
new_color = new_color + 1
old_color = graph[row][col]
dfs(row, col, graph, old_color, new_color)
return graph
4. 백트래킹
백트래킹 문제는 해를 찾는 도중 막히면, 되돌아가서 다시 해를 찾아가는 기법의 아이디어를 활용한 문제입니다. 여기서는 선택 -> 재귀 -> 복구 패턴을 사용해 문제를 해결합니다.
이 문제의 경우에는 그래프가 아니여도, 주로 DFS를 사용합니다.
# n에서 길이 k인 순열 생성
def permutations_n_k(n, k):
used = [False] * (n + 1)
path = []
out = []
def dfs(depth):
if depth == k:
out.append(path[:])
return
for x in range(1, n + 1):
if not used[x]:
used[x] = True
path.append(x)
dfs(depth + 1)
path.pop()
used[x] = False
dfs(0)
return out
print(permutations_n_k(3, 2))
# [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
5. 그래프 순회 문제
그래프 순회는 하나의 시작 노드에서 출발해, 그 노드로부터 도달 가능한 모든 노드를 방문하는 문제입니다. 주로 방문 순서 출력 문제가 출력됩니다.
# DFS 방문 순서 출력
def dfs_traversal(graph, start):
visited = set()
order = []
def dfs(u):
visited.add(u)
order.append(u)
for v in graph.get(u, []):
if v not in visited:
dfs(v)
dfs(start)
return order
graph = {1:[2,3], 2:[4], 3:[5], 4:[], 5:[]}
print(dfs_traversal(graph, 1)) # [1,2,4,3,5] (인접 리스트 순서에 따라 달라짐)
6. 사이클 찾기 문제
사이클 찾기 문제는 시작점과 방문점이 같은 경우가 존재하는지를 찾는 문제입니다. 사이클이란 DFS 탐색 중, 현재 재귀 경로(on_path)에 포함된 노드를 다시 방문하는 경우를 의미합니다.
# 방향 그래프 사이클 존재 여부 문제
def has_cycle_directed(graph, n):
visited = [False] * (n + 1)
on_path = [False] * (n + 1)
def dfs(u):
visited[u] = True
on_path[u] = True
for v in graph.get(u, []):
if not visited[v]:
if dfs(v):
return True
elif on_path[v]:
return True # 현재 경로(on_path)에 다시 들어오면 사이클
on_path[u] = False
return False
for i in range(1, n + 1):
if not visited[i]:
if dfs(i):
return True
return False
# 사용 예시: 1->2->3->1 사이클
graph = {1:[2], 2:[3], 3:[1], 4:[]}
print(has_cycle_directed(graph, 4)) # True
Leave a comment