깊이 우선 탐색(DFS) 구현 방법

• DFS는 스택을 사용하여 이미 방문한 노드를 추적합니다. 재귀 호출을 사용하여 스택 구현을 내재화할 수 있습니다.

Copy
def dfs(graph, start, visited=[]):
    if start not in visited:
        visited.append(start)

        for next in graph[start]:
            if next not in visited:
                dfs(graph, next, visited)

    return visited

• 현재 노드에서 방문하지 않은 인접 노드를 찾아 계속해서 탐색을 진행합니다.

Copy
for next in graph[start]:
    if next not in visited:
        dfs(graph, next, visited)

1. 시간 복잡도: (O(V + E))

   • 여기서 V는 정점의 수, E는 간선의 수를 나타냅니다. 각 정점은 한 번씩 방문되며, 각 간선은 두 번 검사됩니다(양방향).

2. 비순환 그래프에서의 효율성: DFS는 비순환 그래프에서 모든 노드를 방문하는 데 효과적입니다.

3. 순환 그래프에서의 주의점: 순환 경로가 있는 그래프에서는 무한 루프에 빠질 위험이 있으므로, 이를 방지하기 위한 추가적인 메커니즘이 필요할 수 있습니다.