문제
BOJ 24444 - 알고리즘 수업 - 너비 우선 탐색 1
N개의 정점과 M개의 간선으로 이루어진 그래프에서, R에서 시작하는 BFS 방문 순서를 구하라. 인접 정점은 오름차순으로 방문한다.
입력
첫째 줄에 N, M, R, 이후 M줄에 간선 정보가 주어진다.
출력
각 정점의 방문 순서를 출력한다 (방문하지 않으면 0).
예제
| 입력 | 출력 |
|---|---|
5 5 1 1 4 1 2 2 3 2 4 3 4 | 1 2 4 3 0 |
풀이
인접 리스트를 오름차순 정렬 후 BFS를 수행하며 방문 순서를 기록한다.
- 인접 리스트를 오름차순 정렬한다
- R에서 BFS를 시작하며 방문 순서 카운터를 증가시킨다
- 각 정점에 방문 순서를 기록한다
핵심 아이디어: 인접 리스트를 정렬하면 BFS에서 자연스럽게 오름차순으로 방문하게 된다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day558BOJ24444너비우선탐색 {
static int N, M;
static List<List<Integer>> l = new ArrayList<>();
static int[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
visited = new int[N + 1];
for (int i = 0; i <= N; i++)
l.add(new ArrayList<>());
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
l.get(A).add(B);
l.get(B).add(A);
}
for (int i = 1; i <= N; i++)
Collections.sort(l.get(i));
bfs(R);
for (int i = 1; i <= N; i++)
System.out.println(visited[i]);
}
static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
int cnt = 1;
q.offer(start);
visited[start] = cnt++;
while (!q.isEmpty()) {
int a = q.poll();
for (int i = 0; i < l.get(a).size(); i++) {
int nextV = l.get(a).get(i);
if (visited[nextV] != 0)
continue;
q.offer(nextV);
visited[nextV] = cnt++;
}
}
}
}복잡도
- 시간: O((V + E) log V)
- 공간: O(V + E)