깊이 우선 탐색(Depth First Search, DFS)

📔 깊이 우선 탐색(DFS) 이란

• 깊이를 우선으로 하여 탐색을 수행하는 알고리즘
• 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법!
• ex) 미로탐색 - 막힐 때 까지 계속 가다가 막다른 길이 나오면 가장 최근의 갈림길로 돌아가 다시 길을 찾는 것!
• 경로를 찾고 싶을 떄
• 스택와 그래프로 해결한다. ( 재귀함수를 써도 됨 )
  스택으로 사용시 이웃 중 가장 뒤에 있는 것부터,
  재귀 사용시 이웃 중 가장 앞에 있는 것부터 탐색한다.

📔 깊이 우선 탐색(DFS) 구현

def dfs(c):
    print(c, end=' ')
    for neighbor in adj[c]:  # c의 이웃 중
        if visited[neighbor] == 0:  # 방문 아직 안한 친구이면
            visited[neighbor] = 1
            dfs(neighbor)


# 인접리스트
# 노드: 1,2,3,4,5,6,7
n = 10
adj = {x: [] for x in range(1, n + 1)}
edges = [
    [1, 2],
    [1, 5],
    [1, 9],
    [2, 3],
    [3, 4],
    [5, 6],
    [5, 8],
    [6, 7],
    [9, 10]
]

# 무방향 그래프이므로 반대쪽도 성립
for edge in edges:
    s, e = edge
    adj[s].append(e)
    adj[e].append(s)

print(adj)

# 1부터 탐색
k = 1
visited = [0] * (n + 1)
visited[k] = 1
print('방문 순서')
dfs(k)