깊이 우선 탐색(DFS)
한 길을 갈 수 있는 데까지 깊이 따라간 뒤, 마지막 갈림길로 돌아가며 그래프를 탐색합니다. 화면의 스택이 바로 그 길입니다.
- 시간 O(V + E)
- 메모리 O(V)
- 스택 사용
용어 설명
- 정점: 그래프의 점. 여기서는 글자가 적힌 원으로 그립니다.
- 간선: 두 정점을 잇는 선. 여기서는 양쪽 방향으로 다닐 수 있습니다.
- 이웃: 한 정점과 간선으로 이어진 정점들. 알파벳 순서로 살펴봅니다.
- 큐: 먼저 들어간 것이 먼저 나옵니다. BFS는 항상 가장 오래 기다린 정점을 꺼냅니다.
- 스택: 마지막에 들어간 것이 먼저 나옵니다. DFS는 항상 가장 최근에 도착한 정점에서 계속 나아갑니다.
- V와 E: 정점과 간선의 개수. O(V + E)는 모든 정점과 간선을 정해진 횟수만큼만 처리한다는 뜻입니다.
0 / 60 단계
- 스택에 있음
- 현재
- 완료
- 탐색 트리 간선
- 건너뛴 간선
A에서 시작합니다. 재생을 누르거나 한 단계씩 진행하세요.
스페이스바: 재생 또는 일시정지. 좌우 화살표 키: 단계 이동. Home과 End 키: 처음과 끝으로 이동.
해 보세요: 사이클이 있는 그래프를 골라 보세요. 점선 간선은 모두 이미 스택에 있거나 완료된 정점으로 돌아가며, 그 간선이 사이클을 닫습니다.
작동 방식
DFS는 아직 보지 않은 첫 번째 이웃으로 자기 자신을 호출하고, 다시 그 정점의 첫 번째 새 이웃으로 호출하는 식으로 이어갑니다. 정점에 새 이웃이 남지 않으면 그 호출이 끝나고, DFS는 한 단계 돌아가 그곳의 다음 이웃을 시도합니다. 아직 끝나지 않은 호출들이 스택을 이루며, 이 스택은 항상 시작 정점에서 현재 정점까지의 길입니다. 정점 옆의 숫자는 방문한 순서입니다.
언제 쓰면 좋을까
어디까지 갈 수 있는지 알아보거나, 사이클을 찾거나, 미로를 걷거나, 서로 의존하는 작업의 순서를 정할 때 DFS를 쓰세요. 가장 짧은 길은 찾지 못합니다.