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

• 스택 or 재귀를 사용해서 구현한다.

DFS는 완전 탐색이기 때문에 모든 경우를 탐색한다.

인접 행렬(adjacency matrix)을 이용한 깊이 우선 탐색(DFS, Depth-First Search) 예제

adj = [[0] * 13 for _ in range(13)]
adj[0][1] = adj[0][7] = 1
adj[1][2] = adj[1][5] = 1

# for row in adj:
#     print(row)


def dfs(now):
    for nxt in range(13):
        if adj[now][nxt]:
            dfs(nxt)


dfs(0)

먼저, adj 리스트는 13x13 크기의 이차원 리스트로, 모든 원소를 0으로 초기화함. 그리고 adj[0][1], adj[0][7], adj[1][2], adj[1][5]의 값을 1로 변경. 이는 무방향 그래프에서 정점 0과 정점 1, 정점 7이 간선으로 연결되어 있으며, 정점 1과 정점 2, 정점 5가 간선으로 연결되어 있다는 의미.

다음으로 dfs 함수는 현재 노드(now)를 인자로 받아, 해당 노드에서 시작하는 깊이 우선 탐색을 수행. dfs 함수는 현재 노드에서 인접한 모든 노드들을 방문하며, 재귀적으로 dfs 함수를 호출. 이때, adj[now][nxt]가 참(True)이면, 즉 현재 노드와 인접한 노드들 중에서 방문하지 않은 노드가 있다면 해당 노드를 방문.

마지막으로 dfs(0)을 호출하여, 정점 0에서 시작하는 깊이 우선 탐색을 수행합니다. 이때, 방문한 노드들은 재귀 호출이 끝나면서 스택에서 Pop 되는 순서대로 출력됨.