DFS

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

스택 이용 시 주의 사항
스택에 삽입 => 방문처리(스택에 중복으로 넣는 것 방지하기 위해)
스택에서 출력 => 실제 방문 순서

결론: 스택에 삽입 시 방문 처리하고, 방문 순서는 스택 출력 시이다.

재귀

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)