이 포스트는 책 '이것이 코딩 테스트다'를 토대로 작성하였습니다.

📌 Depth-First Search(DFS)

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

👉 DFS 알고리즘

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

🧐 예시

다음과 같은 그래프를 노드 1을 시작으로 DFS를 이용해 탐색한다.

step1

• 시작 노드인 '1'을 스택에 삽입하고 방문처리를 한다.
  

step2

• 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '2', '3', '8' 중 가장 작은 노드 '2'를 스택에 넣고 방문 처리를 한다.
  

step3

• 스택의 최상단 노드인 '2'에 방문하지 않은 인접노드 '7'을 스택에 넣고 방문 처리를 한다.
  

step 4 ~ step 5

• 이전 과정들과 동일하게 처리
  

⭐ step 6

• 스택의 최상단 노드인 '8'에 방문하지 않은 인접 노드가 없다.
  따라서 스택에서 '8'번 노드를 꺼낸다.
  

step 7 ~ step 9

• step 6과 동일하게 처리한다.
  

step 10

• 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '3'을 스택에 넣고 방문 처리한다.
  

step 11

• 스택의 최상단 노드인 '3'에 방문하지 않은 인접 노드 '4, '5'중 가장 작은 노드인 '4'를 스택에 넣고 방문 처리를 한다.
  

step 12

• 스택의 최상단 노드인 '4'에 방문하지 않은 인접 노드 '5'를 스택에 넣고 방문 처리한다.
  

step 13

• 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드 스택에서 꺼낸다.
  

결과

노드의 탐색 순서는 스택에 들어간 순서이므로,
노드의 탐색 순서는

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

이다.

⌨ DFS 코드

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end='')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[v]:
            dfs(graph, i, visited)