들어가기
먼저 그래프에서의 탐색 방법들에 대해서 배워보기 전에 그래프란 무엇인지에 대해서 간략하게나마 알 필요가 있다.
그래프란?
→ 노드(vertex)와 간선(edge)을 가지고 만들어지는 비선형 데이터 구조를 말한다.
그래프는 주로 데이터 간의 관계를 표현할 때 사용된다.
그래프에서 탐색 경로를 찾는 방법은 크게 총 2가지가 있다.
- 더 이상 탐색할 노드가 없을 때까지 계속 타고 들어간다. 타고 들어가다가 더 이상 탐색할 노드가 존재하지 않으면 백트레킹을 통해 최근 방문했던 노드로 되돌아간다. 그 후 그 노드로부터 가지 않은 노드를 방문한다. 이 과정을 그래프에서 모든 노드를 탐색할 때까지 반복한다. (깊이 우선 탐색 DFS)
- 현재 위치에서 가장 가까운 노드부터 모두 방문하고 그 이후 다음 노드로 넘어간다. 넘어간 노드로부터 또 가장 가까운 노드를 탐색해 방문한다. 이 과정을 그래프에서 모든 노드를 탐색할 때까지 반복한다. (너비 우선 탐색 BFS)
이번 게시글에서는 깊이 우선 탐색 (Depth-First-Search)에 대해 알아보려한다.
깊이 우선 탐색 (DFS)
DFS는 시작 노드부터 탐색을 시작해서 간선을 따라 타고 들어가서 가장 깊이 있는 노드까지 이동하면서 차례대로 방문한다. 더 이상 들어갈 수 없는 (탐색할 노드가 없는) 노드까지 방문했으면, 이전에 방문했던 노드로 백트레킹해서 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드로 다시 타고 들어가 차례대로 방문한다.
DFS 과정 살펴보기
* 최초 탐색 전, 시작 노드를 설정하고 스택에 먼저 시작하는 노드를 push한다.
(스택에 있는 노드들은 아직 방문하지는 않았지만 차례대로 방문할 예정인 노드들을 의미한다.)
01
스택이 비어있는 지 확인. 스택이 비었으면 탐색 종료.
(스택이 비었다 == 방문할 수 있는 모든 노드를 탐색했다)
02
스택에서 노드를 pop한다. 스택은 LIFO(Last-In, First-Out) 구조 이므로, 여기서 pop한 노드는 가장 마지막에(최근에) push한 노드이다.
03
pop한 노드의 방문 여부를 확인한다. (visited에 포함되어있는지) 아직 방문한 적 없다면, 방문 처리.
04
그 후 현재 다루는 노드와 인접한 모든 노드들을 확인한다. 그 중 아직 방문하지 않은 노드인 경우 스택에 push 해준다.
📌 위의 DFS 과정이 얼핏보면 Stack 기반으로 DFS를 구현했을 때의 과정만을 설명한 것처럼 보인다. 그러나 재귀 함수 사용해서 DFS를 구현하는 것 역시 위와 같은 Flow를 따른다. 직접적으로 stack을 사용하는 것은 아니지만, 재귀 함수를 호출할 때마다 호출한 함수들은 시스템 스택이라는 곳에 쌓이기 때문에 결국 모두 공통된 흐름을 따라간다.
DFS 핵심 알아보기
가장 깊은 노드까지 방문한 후, 더 이상 방문할 노드가 없다면 최근 방문한 노드로 돌아가고, 돌아간 노드에서 방문할 노드가 있는 지 확인한다
DFS를 stack을 사용해서 구현하는 과정 공부하기
노드 상태 처리 (색)
- White : 아직 탐색하지 않은 노드
- Skyblue : 이미 탐색한 노드
Step 1
시작 노드를 설정하고, 스택에는 시작 노드를 push 해준다. 시작노드는 무조건적으로 가장 먼저 방문할 노드이다.
Step 2
시작노드인 A를 방문하는 과정을 수행한다. Stack에 들어있는 A 노드를 pop해준 후 방문했던 노드인 지 확인한다. 아직 A노드는 방문하지 않았으므로 방문 처리한다. (A 노드 하늘색 처리 & visited에 push)
그 후, A 노드와 인접하고, 아직 방문하지 않은 B, D, E를 Stack에 push한다.
Step 3
Step 2와 같은 방식으로 진행한다. Stack에서 B pop한 후, 방문했는지 확인. 아직 방문하지 않았기에 방문 처리.
그 후, B 노드와 인접하고 아직 방문하지 않은 E를 Stack에 push한다.
Step 4
같은 방식으로 진행.
Step 5
같은 방식으로 진행.
Step 6
같은 방식으로 진행한다. D는 더 이상 방문하지 않은, 인접 노드가 없으므로 Stack에 아무것도 push 하지 않는다.
Step 7
Stack에서 D, E, D를 순서대로 pop한다. 새 노드 모두 이미 방문했던 노드이기 때문에 아무 작업도 따로 하지 않는다.
최종적으로, Stack이 비어서 더이상 탐색할 수 없는 상황이므로 과정은 종료된다.
→ 결과적으로 탐색 결과는 A > B > E > C > D 이다.
DFS를 stack을 사용해서 구현해보기 [파이썬]
graph = {
'A': ['B', 'D', 'E'],
'B': ['E'],
'C': ['D'],
'D': [],
'E': ['C', 'D'],
}
# DFS 함수를 정의합니다.
def dfs(graph, start):
visited = set() # 방문한 노드를 저장할 set
stack = [start] # 시작 노드를 스택에 추가
while stack:
node = stack.pop() # 스택에서 가장 최근에 추가된 노드를 가져옴
if node not in visited:
visited.add(node) # 방문한 노드를 저장
print(node, end=' ')
for next_node in graph[node]:
if next_node not in visited:
stack.append(next_node) # 다음에 방문할 노드를 스택에 추가
# DFS를 호출합니다.
dfs(graph, 'A')DFS를 재귀 함수를 사용해서 구현하는 과정 공부하기
노드 상태 처리 (색)
- White : 아직 방문하지 않은 노드
- Skyblue : 방문은 했으나 아직 방문할 하위 노드들이 남아있는 상태의 노드
- Grey : 더이상 방문할 하위 노드가 없는 노드
Step 1
시작노드는 A이므로, 먼저 dfs(A)를 호출한다. dfs(A)는 A노드를 방문 처리하고, 내부적으로 A노드와 인접한 노드 중 낮은 알파벳에 해당하는 D노드를 방문하기 위해 dfs(D)를 재귀적으로 호출한다.
dfs(A)를 호출 중에 dfs(D)를 재귀 호출했기 때문에 dfs(A)는 완전히 종료된 상태가 아니므로 스택에 쌓여있게 된다.
Step 2
이전 스탭과 동일한 과정으로 진행된다. dfs(D)는 D노드를 방문처리하고 내부적으로 인접한 두 노드(B, C) 중 더 낮은 B노드를 방문하기 위해 dfs(B)를 재귀적으로 호출한다.
이전과 마찬가지로, dfs(D)는 시스템 스택에 쌓이게 된다.
Step 3
이전 스텝과 동일하게 진행. dfs(B)는 B를 방문처리. 그 후 C노드를 방문하기 위해 dfs(C)를 재귀적으로 호출.
dfs(B)는 시스템 스택에 쌓이게 됨.
Step 4
dfs(C)를 실행해서 C노드 방문처리. 그 이후 인접 노드 접근을 위한 재귀 호출을 해야 하지만, C노드는 더 이상 깊이 들어갈 인접한 노드들이 없음. 따라서 추가적인 재귀호출 없이 함수를 종료한다.
그래서 dfs(C)는 시스템 스택에 들어갔다가 바로 나오게 된다.
Step 5
dfs(B)에서 재귀 호출되었던 dfs(C)가 종료되었으므로 다시 dfs(B)로 돌아가서 함수를 이어서 진행한다. B노드 역시 인접 노드가 더 이상 없으므로 dfs(B) 함수를 종료한다.
Step 6
이전 스텝과 동일하게 dfs(B)가 종료되면서 다시 dfs(D)로 돌아가서 함수가 진행.
D노드의 추가적인 인접 노드가 없으므로 dfs(D) 함수도 종료.
Step 7
dfs(D)가 종료되었으므로 dfs(A)로 돌아가서 함수가 진행된다.
A노드는 아직 방문한 적 없는 E노드와 인접해있으므로 dfs(E)를 재귀적으로 호출한다.
Step 8
dfs(E)를 실행한다. E노드를 방문처리하고, 인접노드가 더 이상 없기 때문에 함수를 종료한다.
모든 노드가 방문되었기 때문에 dfs(A)도 뒤따라서 종료되며 모든 과정이 종료된다.
→ 결과적으로, 탐색 결과는 A > D > B > C > E 이다.
DFS를 재귀 함수를 사용해서 구현해보기 [파이썬]
N = 5 # node수
V = 1 # 시작노드
# 자기 자신과는 False, Index 0은 모두 False
graph = [
[False, False, False, False, False, False], # index 0을 사용하지 않음
[False, False, False, False, True, True], # 1: {4, 5}
[False, False, False, True, False, False], # 2: {3}
[False, False, False, False, False, False], # 3: {}
[False, False, True, True, False, False], # 4: {2, 3}
[False, True, False, False, True, False], # 5: {1, 4}
]
# 설정된 그래프에서 방문한 곳을 True로 설정
visited = [False] * (N + 1)
def dfs(V) :
visited[V] = True
print(V, end=" ")
for i in range(1, N + 1) :
# visited[i]: 인접한 노드가 방문처리된 상태인지 확인
# graph[V][i]: 현재노드인 graph[V]의 인접한 노드가 있는 지 확인
if not visited[i] and graph[V][i] :
dfs(i) # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)
dfs(V)from collections import defaultdict
# [key : value] 형식으로 구성. 그러나 모든 key에 대해 기본(default) 값을 설정.
graph = [
['A', 'B'],
['B', 'C'],
['C', 'D'],
['D', 'E'],
]
start = 'A'
#* 그래프를 인접리스트로 변환
adjacent_list = defaultdict(list)
for u, v in graph :
adjacent_list[u].append(v)
#* DFS 탐색 함수 (재귀)
# node: 현재 노드, visited: 방문한 노드들, result: 노드 탐색 순서
def dfs(node, visited, result) :
visited.add(node) # 현재 노드를 방문한 것으로 표시
result.append(node) # 현재 노드를 결과 리스트에 추가
# get method: 딕셔너리에서 키에 해당하는 값을 찾아 반환.
# 첫 번째 인자는 찾고자 하는 키(node)를 지정하고,
# 두 번째 인자는 키가 딕셔너리에 없을 경우 반환할 기본값([])을 지정합니다.
for neighbor in adjacent_list.get(node, []) : #* 현재 노드와 인접한 노드 순회
if neighbor not in visited : # 아직 방문하지 않은 노드라면
dfs(neighbor, visited, result) #* 재귀적으로 탐색
# DFS 순회 결과 반환
visited = set()
result = []
dfs(start, visited, result)
print(result)
Stack으로 구현한 DFS보다 훨씬 코드가 간결하고 짧은 것을 확인할 수 있다. 현재 예시 코드에서는 graph를 위에서 설명한 예시 그래프에 맞게 내가 임의로 설정해서 구현했지만, 충분히 input 값을 받아서 원하는 그래프 모양대로 그때그때 만들어서 DFS 결과값을 출력하는 것도 당연히 가능하다.
마무리하기
이렇게 DFS를 어떻게 구현하는 지 stack을 사용하는 방법과 재귀 함수를 사용하는 방법, 총 2가지를 알아보았다.
대부분 코딩테스트에서 DFS를 구현해서 활용해야 할 때 stack을 사용하는 방식보다 재귀 함수를 사용하는 방식을 더 선호하기 때문에 stack 방식은 그냥 개념 공부 및 참고용으로 공부하면 좋을 것 같다.
재귀 함수를 사용하는 방식은 자주 사용될 것이기 때문에 꼭 잘 알아두자!