DFS

dfs의 풀이방법은 2가지(재귀, 스택)이다.
그래프 간선 정보가 오름차순으로 정렬되어 있다는 가정 하에,
재귀 -> 인접한 노드 중 작은 노드 번호 우선 dfs 탐색 (부모 -> 왼쪽 -> 오른쪽)
스택 -> 인접한 노드 중 큰 노드 번호 우선 dfs 탐색 (부모 -> 오른쪽 -> 왼쪽)
탐색 순서만 다를 뿐 dfs 원리는 동일하다.

재귀 이용 시 주의 사항

• 스택에 삽입 => 실제 방문
• 노드 내 리스트의 앞쪽부터 방문

스택 이용 시 주의 사항

• 스택에 삽입 => 방문 가능 지역 처리 처리 (중복 방문 방지)
• 스택에서 출력 => 실제 방문
• 노드 내 리스트의 뒤쪽부터 방문 (후입선출(LIFO) 특성)

(스택에서 출력시에 실제 방문하는 이유)
방문가능지역 검사에서 만난 순서와 실제 탐색 지역의 순서가 다르기 때문

재귀

graph = [
    [],
    [2,3],# 그래프는 1번 노드부터 존재
    [1,4,5],
    [1,6,7],
    [2],
    [2],
    [3],
    [3,8,9],
    [7,9],
    [7,8]
]
visited = [False] * 10 # 배열의 인덱스가 노드 번호임

def dfs_rec(graph, i, visited):
    visited[i] = 1 # i번 노드 방문 처리
    print(i, end=" ")
    
    for j in graph[i]: # 현재 노드에 연결된 다른 노드들 dfs 로 탐색
        if visited[j] == 0: # 방문하지 않은 노드인 경우
            visited[j] = 1 # 방문 처리
            dfs_rec(graph, j, visited) # 해당 노드에 대해 다시 dfs 탐색 

print("방문 순서")
dfs_rec(graph, 1, visited) # 1번 노드부터

스택

graph = [
  [],
  [2,3],# 그래프는 1번 노드부터 존재
  [1,4,5],
  [1,6,7],
  [2],
  [2],
  [3],
  [3,8,9],
  [7,9],
  [7,8]
]
visited = [0] * 10

from collections import deque
def dfs_stack(graph, r, visited):
    stack = deque()
    # 스택에 시작 노드 삽입 & 방문 처리
    stack.append(r)
    visited[r] = True
    # 스택 이용해 dfs 탐색
    while stack:
        # 스텍에서 하나의 노드를 뽑아 출력
        v = stack.pop()
        print(v)
        # 해당 노드와 연결된, 아직 방문하지 않은 원소들을 스택에 삽입
        for i in graph[v]:
            if visited[i] == 0: # 방문 예정짓지 않은 노드인 경우
                stack.append(i)
                visited[i] = True # 방문 예정 처리
        
dfs_stack(graph, 1, visited)

문제 유형에 따른 풀이 방법 선택

같은 dfs 풀이라도 문제에서 의도하는 탐색 순서에 따라 방법을 선택해야 한다.
아래 N 과 M (1) 문제에서 의도하는 탐색 순서는 재귀를 활용한 DFS 방법(부모->왼쪽->오른쪽)이다.
스택을 이용해서도 풀 수 있으나 reverse() 를 사용하여 기존의 탐색 순서(부모->오른쪽->왼쪽)를 직접 변경(부모->왼쪽->오른쪽)해주어야 한다.