문제 27
DFS
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 간선으로 이루어진 무방향 그래프가 있다.
정점 $S$에서 DFS를 시작하여 정점을 방문하는 순서대로 출력하라.
방문할 수 있는 정점이 여러 개라면 번호가 작은 정점을 먼저 방문한다.
입력
첫 번째 줄에 세 정수 $N$, $M$, $S$가 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000; 0 \le M \le 200\,000; 1 \le S \le N)$
두 번째 줄부터 $M$개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호를 의미하는 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v)$
같은 간선은 두 번 이상 주어지지 않는다.
출력
정점 $S$에서 DFS를 수행했을 때 방문하는 정점을 순서대로 출력한다.
정점 번호는 공백으로 구분한다.
예제 입력 1
6 7 1 1 2 1 3 2 4 2 5 3 5 3 6 5 6
예제 출력 1
1 2 4 5 3 6
공식 해설
각 정점의 인접 리스트를 정점 번호순으로 정렬한 뒤 $S$에서 깊이 우선 탐색을 시작한다. 정점에 처음 들어갈 때 방문 표시를 하고 번호를 기록한다.
이웃을 작은 번호부터 확인하여 아직 방문하지 않은 정점으로 내려간다. 그 이웃에서 시작한 탐색이 모두 끝난 뒤 다음 이웃을 확인하므로 문제에서 요구한 DFS 순서가 된다. $S$와 연결되지 않은 정점에서는 새 탐색을 시작하지 않는다.
재귀 DFS는 자식의 탐색이 끝나면 부모의 다음 이웃부터 이어서 탐색한다. 반복문으로 구현한다면 스택에 현재 정점과 다음에 확인할 이웃의 위치를 함께 저장하여 같은 순서를 재현할 수 있다.
정점 $v$의 차수를 $d_v$라 할 때 정렬을 포함한 시간복잡도는 $O(N+M+\sum_v d_v\log(d_v+1))$, 공간복잡도는 $O(N+M)$이다.
구현 · 언어별 풀이
C++ 구현
인접 리스트는 vector<vector<int>>로 저장하고 각 리스트를 sort한다. 반복문으로 구현한다면 stack<pair<int, int>>에 정점과 다음 이웃 위치를 저장한다. 방문 표시는 정점에 처음 들어갈 때 하고, 탐색 종료 순서가 아닌 진입 순서를 출력한다.
C 구현
정렬된 인접 목록과 정점·다음 간선 위치를 담은 DFS 스택을 사용한다. 새 정점에 진입할 때 방문 순서를 기록하고, 자식에서 복귀하면 부모의 다음 간선으로 진행한다.
Python 구현
인접 리스트를 정렬하고 스택에 (정점, 다음 이웃 위치)를 저장한다. 이웃을 하나씩 확인하고 자식의 탐색을 마친 뒤 다음 이웃으로 진행한다. 모든 이웃을 넣자마자 방문 처리하면 재귀 DFS와 순서가 달라질 수 있다.
Java 구현
인접 배열을 정렬하고 정점·진행 위치를 담는 int 배열 스택을 둔다. 정점 진입 시 방문 번호를 부여하고, 각 프레임의 이웃을 하나씩 확인한다.
Rust 구현
인접 Vec을 sort_unstable()하고 (정점, 다음 이웃 위치) 프레임을 Vec에 저장한다. top 프레임의 위치를 갱신한 뒤 자식 프레임을 넣어 재귀 순서를 재현한다. push 전에 top의 가변 borrow를 끝낸다.
JavaScript 구현
인접 리스트는 adj[v].sort((a, b) => a - b)로 숫자순 정렬한다. 기본 문자열 정렬로는 정점 $10$이 $2$보다 앞에 나올 수 있다.
명시적 스택에 정점과 다음 이웃 위치를 저장하고, 아직 방문하지 않은 이웃 하나를 찾으면 그 정점으로 내려간다. 해당 정점의 이웃을 모두 살핀 뒤 프레임을 꺼내면 재귀 DFS의 순서를 보존한다. 모든 이웃을 미리 방문 표시하며 쌓는 방식과 구분한다.