소개
어떤 문제를 해결하나요
미로에서 나가는 길 찾기, 그래프에 순환이 있는지 확인하기, 서로 의존하는 작업 순서 정하기는 모두 다른 것을 시도하기 전에 경로 하나를 갈 수 있는 데까지 따라가야 합니다. 그것이 깊이 우선 탐색입니다.
일상 속 비유
깊이 우선 탐색은 실뭉치를 들고 동굴을 탐험하는 방법입니다. 굴 하나를 갈 수 있는 데까지 깊이 따라갑니다. 막다른 곳에서는 실을 따라 마지막 갈림길로 돌아가 다음 굴을 시도합니다. 탐험한 굴은 표시해 두어 두 번 걷지 않습니다.
visited.add(node)🧵 이 굴을 탐험했다고 표시for neighbor in graph[node]:🔀 여기서 갈라지는 굴을 하나씩 보기depth_first(neighbor, visited)⬇️ 탐험 안 한 첫 굴로 더 깊이return order↩️ 막다른 곳: 실을 따라 돌아가기깊이 우선 탐색(DFS)은 되돌아오기 전에 가지 하나를 최대한 깊이 따라가며 그래프를 탐색하며, 보통 재귀나 스택을 씁니다.
핵심 포인트
visited.add(node)는 노드를 표시하므로 순환이 끝없는 재귀를 일으킬 수 없습니다.for neighbor in graph[node]:는 이웃을 하나씩 차례로 봅니다.order.extend(depth_first(neighbor, visited))는 다음 이웃으로 가기 전에 이웃 아래의 가지 전체를 탐색합니다.- B 의 가지가 먼저 끝나므로 결과는 C 보다 D 를 먼저 방문합니다.
언제 사용하나요?
- 경로 하나 찾기, 백트래킹으로 미로와 퍼즐 풀기.
- 순환 감지와 의존성 있는 작업 순서 정하기(위상 정렬).
- 그래프의 연결된 모든 부분 탐색하기.
필요 없는 경우
- 최단 경로가 필요한 경우: 깊이 우선 탐색은 긴 경로를 먼저 찾을 수 있으니 너비 우선 탐색을 씁니다.
- 아주 깊은 그래프: 재귀가 Python 의 한도에 걸릴 수 있으니 명시적인 스택을 씁니다.
Python의 깊이 우선 탐색(DFS) 시각화
O(V + E)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
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 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
가변 기본 인수 쓰기
visited=set() 은 서로 다른 호출 사이에서 공유됩니다.
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
- Count Islands Count groups of connected land cells in a grid. 보통
- Strongly Connected Components Count groups of nodes that can all reach each other. 어려움
- Longest Path in a DAG Find the heaviest path in a task dependency graph. 어려움