Python 알고리즘

Python의 깊이 우선 탐색(DFS)

이 레슨에서는 재귀 함수로 구현한 깊이 우선 탐색으로 그래프를 탐색합니다.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

미로에서 나가는 길 찾기, 그래프에 순환이 있는지 확인하기, 서로 의존하는 작업 순서 정하기는 모두 다른 것을 시도하기 전에 경로 하나를 갈 수 있는 데까지 따라가야 합니다. 그것이 깊이 우선 탐색입니다.

일상 속 비유

깊이 우선 탐색은 실뭉치를 들고 동굴을 탐험하는 방법입니다. 굴 하나를 갈 수 있는 데까지 깊이 따라갑니다. 막다른 곳에서는 실을 따라 마지막 갈림길로 돌아가 다음 굴을 시도합니다. 탐험한 굴은 표시해 두어 두 번 걷지 않습니다.

동굴 탐험에서 코드로
visited.add(node)🧵 이 굴을 탐험했다고 표시
for neighbor in graph[node]:🔀 여기서 갈라지는 굴을 하나씩 보기
depth_first(neighbor, visited)⬇️ 탐험 안 한 첫 굴로 더 깊이
return order↩️ 막다른 곳: 실을 따라 돌아가기
먼저 깊이 가고, 그다음 되돌아와 다음 가지를 시도합니다.
한 문장으로

깊이 우선 탐색(DFS)은 되돌아오기 전에 가지 하나를 최대한 깊이 따라가며 그래프를 탐색하며, 보통 재귀나 스택을 씁니다.

핵심 포인트

  1. visited.add(node) 는 노드를 표시하므로 순환이 끝없는 재귀를 일으킬 수 없습니다.
  2. for neighbor in graph[node]: 는 이웃을 하나씩 차례로 봅니다.
  3. order.extend(depth_first(neighbor, visited)) 는 다음 이웃으로 가기 전에 이웃 아래의 가지 전체를 탐색합니다.
  4. B 의 가지가 먼저 끝나므로 결과는 C 보다 D 를 먼저 방문합니다.

언제 사용하나요?

  • 경로 하나 찾기, 백트래킹으로 미로와 퍼즐 풀기.
  • 순환 감지와 의존성 있는 작업 순서 정하기(위상 정렬).
  • 그래프의 연결된 모든 부분 탐색하기.

필요 없는 경우

  • 최단 경로가 필요한 경우: 깊이 우선 탐색은 긴 경로를 먼저 찾을 수 있으니 너비 우선 탐색을 씁니다.
  • 아주 깊은 그래프: 재귀가 Python 의 한도에 걸릴 수 있으니 명시적인 스택을 씁니다.

Python의 깊이 우선 탐색(DFS) 시각화

O(V + E)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

예제 코드

코드 실행 →
main.py
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}

def depth_first(node, visited=None):
    visited = visited or set()
    visited.add(node)
    order = [node]
    for neighbor in graph[node]:
        if neighbor not in visited:
            order.extend(depth_first(neighbor, visited))
    return order

print(depth_first("A"))
이 예제의 실행 버튼 만들기

실행 결과

['A', 'B', 'D', 'C', 'E']

코드 설명

집합 visited는 방문한 정점을 기억해서, 그래프에 사이클이 있을 때 중복 방문과 무한 반복을 막습니다. 각 재귀 호출은 아직 방문하지 않은 이웃으로 내려가므로, 프로그램은 A, B, D를 방문한 뒤 돌아와서 C와 E를 방문합니다. 호출 스택이 알고리즘의 스택 역할을 하며, 복잡도는 O(V + E)입니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

가변 기본 인수 쓰기

visited=set() 은 서로 다른 호출 사이에서 공유됩니다.

문제
def depth_first(node, visited=set()):
수정
def depth_first(node, visited=None):
    visited = visited or set()

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지