[Python] DFS

DFS(Depth-First Search)

> 깊이 우선 탐색으로, 그래프에서 수직 우선으로 탐색한다.

• 그래프: 노드(Node)와 간선(Edge)으로 표현
• 그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것. 두 노드가 간선으로 연결되어 있을 때, 두 노드는 인접하다(Adjacent)라고 한다.
• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식으로, 연결되지 않은 노드끼리는 무한의 비용을 가정하여 값을 초기화한다.
  * 파이썬은 배열을 리스트 자료형으로 표현 가능하므로, 리스트로 구현하는 방식을 선택한다.
• 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식으로, 각 노드마다 연결된 노드에 대한 정보를 연결하여 저장

BFS와 DFS의 탐색 순서 차이

 

> DFS의 스택 자료구조를 활용한 동작 과정

    * 스택에 노드를 쌓는 과정을 1개씩(노드 번호가 작은 순으로) 진행하는 경우

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

> 스택으로 구현 시 여러 개의 노드를 한 번에 스택에 쌓는 방법

1. 탐색 시작 노드를 스택에 삽입하고, 즉시 꺼내 해당 노드를 탐색 노드에 저장
2. 탐색 노드를 방문하지 않았다면 방문 처리하고, 모든 인접 노드 중 방문하지 않은 인접 노드를 모두 스택에 추가
   * 스택의 후입선출(LIFO, Last In First Out) 특성에 의해 DFS 탐색은 역순으로 진행됨.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

> 재귀를 이용하여 간결하게 코드 표현이 가능하다.

• 재귀: 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘
• 수학적 귀납법: '1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다'가 참이면, '모든 도미노가 쓰러진다.'
  * 재귀 함수가 자기 자신을 여러 번 호출하게 되면, 재호출하는 과정에서 중복 연산이 발생하여 시간복잡도가 커지는 등 비효율이 발생할 수 있다.

# 방문 처리를 위한 리스트 생성
visited = [False] * n

# 재귀 함수 생성
def dfs(node):
    visited[node] = True # 방문 처리
    for i in graph[node]: # 노드행 내 원소(노드)를 돌면서 방문 확인
        if not visited[i]:
            dfs(i) # 미 방문 노드 시 재귀 함수 시행

 

Reference

• [바킹독의 실전 알고리즘] 0x0B강 - 재귀
• 이것이 취업을 위한 코딩 테스트다 with 파이썬