문제 28
BFS
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 간선으로 이루어진 무방향 그래프가 있다.
정점 $S$에서 BFS를 시작하여 정점을 방문하는 순서대로 출력하라.
방문할 수 있는 정점이 여러 개라면 번호가 작은 정점을 먼저 방문한다.
입력
첫 번째 줄에 세 정수 $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$에서 BFS를 수행했을 때 방문하는 정점을 순서대로 출력한다.
정점 번호는 공백으로 구분한다.
예제 입력 1
6 7 1 1 2 1 3 2 4 2 5 3 5 3 6 5 6
예제 출력 1
1 2 3 4 5 6
공식 해설
먼저 각 인접 리스트를 정점 번호순으로 정렬한다. $S$를 방문 처리하여 큐에 넣고 다음 과정을 반복한다.
큐의 맨 앞 정점을 꺼내 기록한 뒤, 아직 방문하지 않은 이웃을 작은 번호부터 방문 처리하여 큐의 뒤에 넣는다. 먼저 발견한 정점이 먼저 처리되므로 너비 우선 탐색의 순서를 얻는다.
방문 표시는 꺼낼 때가 아니라 넣을 때 해야 여러 정점에서 같은 이웃을 중복으로 넣지 않는다. 또한 작은 번호 우선 조건은 각 정점의 이웃을 확인하는 순서에 적용한다. 같은 거리의 정점 전체를 따로 정렬하면 다른 탐색 순서가 될 수 있다.
정점 $v$의 차수를 $d_v$라 하면 시간복잡도는 $O(N+M+\sum_v d_v\log(d_v+1))$, 공간복잡도는 $O(N+M)$이다.
구현 · 언어별 풀이
C++ 구현
인접 리스트를 vector<vector<int>>에 저장하고 각각 정렬한다. 탐색 대기열은 queue<int>로 구현한다. 이웃은 방문 표시를 한 뒤 넣어야 같은 정점이 여러 번 큐에 들어가지 않는다.
C 구현
각 인접 목록을 오름차순 정렬하고 배열 큐의 head와 tail로 탐색한다. 방문 표시는 큐에 넣는 순간 한다. 각 정점이 한 번만 들어가므로 큐의 길이는 $N$이면 충분하다.
Python 구현
인접 리스트를 sort()하고 collections.deque의 popleft()로 탐색한다. 넣을 때 방문 번호를 부여하여 같은 정점이 중복으로 큐에 쌓이지 않도록 한다.
Java 구현
정렬된 인접 배열과 ArrayDeque<Integer>를 사용한다. addLast와 removeFirst로 BFS를 진행하고, 큐에 넣을 때 방문 처리한다.
Rust 구현
정렬된 인접 Vec과 VecDeque를 사용한다. 방문 번호가 0인 이웃에 번호를 먼저 부여하고 push_back한다. pop_front로 꺼내며 정렬된 이웃 순서를 유지한다.
JavaScript 구현
인접 리스트를 숫자 비교 함수로 정렬하고 Int32Array(n) 큐에 정점을 넣는다. head와 tail을 각각 읽기·쓰기 위치로 두면 앞 원소를 $O(1)$에 꺼낼 수 있다.
방문 표시는 큐에 넣을 때 한다. 각 정점이 최대 한 번 들어가므로 길이 $N$의 큐면 충분하다.