본문으로 건너뛰기
실습하기

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

1. 스택 사용​

  • DFS는 스택을 사용하여 이미 방문한 노드를 추적합니다. 재귀 호출을 사용하여 스택 구현을 내재화할 수 있습니다.
스택 사용 예시
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

2. 재귀적 탐색​

  • 현재 노드에서 방문하지 않은 인접 노드를 찾아 계속해서 탐색을 진행합니다.
재귀적 탐색 예시
for next in graph[start]:
    if next not in visited:
        dfs(graph, next, visited)

시간 복잡도​

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

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

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

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

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!