문제
N개의 도시와 M개의 단방향 도로(가중치 1)가 주어질 때, 출발 도시 X에서 최단 거리가 정확히 K인 모든 도시를 오름차순으로 출력하라.
입력
첫째 줄에 N, M, K, X가 주어지고, 이후 M줄에 도로 정보가 주어진다.
출력
최단 거리가 K인 도시 번호를 오름차순으로 한 줄에 하나씩 출력한다. 없으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 4 2 1 1 2 1 3 2 3 2 4 | 3 4 |
풀이
BFS로 레벨별 탐색하여 정확히 K번째 레벨의 노드들을 수집한다.
- 인접 리스트를 연결 리스트 방식(Node 클래스)으로 구성한다
- BFS를 K번의 레벨까지만 수행한다 (레벨별로 큐를 분리)
- K번째 레벨에 있는 도시들을 정렬하여 출력한다
핵심 아이디어: 가중치가 1인 그래프에서 BFS의 레벨이 곧 최단 거리이므로, K 레벨까지만 탐색하면 된다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day489BOJ18352특정거리의도시찾기 {
static class Node {
int no;
Node next;
public Node(int no, Node next) {
this.no = no;
this.next = next;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
Node[] nodes = new Node[n + 1];
for (int i = 1; i <= n; i++) {
nodes[i] = new Node(i, null);
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
nodes[a].next = new Node(b, nodes[a].next);
}
System.out.print(bfs(nodes, k, x));
}
private static String bfs(Node[] nodes, int k, int x) {
Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[nodes.length];
q.add(x);
visited[x] = true;
for (int i = 0; i < k; i++) {
Queue<Integer> next = new LinkedList<>();
while (!q.isEmpty()) {
int cur = q.poll();
for (Node node = nodes[cur]; node != null; node = node.next) {
if (!visited[node.no]) {
next.add(node.no);
visited[node.no] = true;
}
}
}
q = next;
}
if (q.size() == 0)
return "-1";
int[] arr = new int[q.size()];
for (int i = 0; i < arr.length; i++) {
arr[i] = q.remove();
}
Arrays.sort(arr);
StringBuilder sb = new StringBuilder();
for (int i : arr) {
sb.append(i + "\n");
}
return sb.toString();
}
}복잡도
- 시간: O(V + E)
- 공간: O(V + E)