https://www.acmicpc.net/problem/18352
문제
어떤 나라에는 1번부터 *N*번까지의 도시와 `M개의 단방향 도로`가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 `X로부터 출발하여 도달할 수 있는 모든 도시중에서,최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램`을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.
입력
첫째 줄에 도시의 개수 *N*, 도로의 개수 *M*, 거리 정보 *K*, 출발 도시의 번호 *X*가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)
둘째 줄부터 *M*개의 줄에 걸쳐서 두 개의 자연수 `A, B가 공백을 기준으로 구분되어 주어진다. 이는 *A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재`한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B*는 서로 다른 자연수이다.
출력
X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 *K*인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.
예제 입력 1
4 4 2 1
1 2
1 3
2 3
2 4
예제 출력 1
4
예제 입력 2
4 3 2 1
1 2
1 3
1 4
예제 출력 2
-1
예제 입력 3
4 4 1 1
1 2
1 3
2 3
2 4
예제 출력 3
2
3+) 예제 입력 4
6 6 3 1
1 2
1 4
2 3
3 1
4 5
5 6+) 예제 출력 4
6풀이
- cyclic한 상황 고려해야 함
BFS
package shortest_path;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main_18352 {
private static int numberOfVertex;
private static int numberOfEdge;
private static int targetDistance;
private static int startVertex;
private static int[] distance;
private static ArrayList<Integer> result = new ArrayList<>();
private static ArrayList<Integer>[] adjacencyList;
public static void main(String[] args) throws IOException {
input();
process();
output();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
numberOfVertex = Integer.parseInt(st.nextToken());
numberOfEdge = Integer.parseInt(st.nextToken());
targetDistance = Integer.parseInt(st.nextToken());
startVertex = Integer.parseInt(st.nextToken());
distance = new int[numberOfVertex + 1];
adjacencyList = new ArrayList[numberOfVertex + 1];
for (int i = 1; i <= numberOfVertex; i++) {
adjacencyList[i] = new ArrayList<>();
}
for (int i = 0; i < numberOfEdge; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
adjacencyList[a].add(b);
}
}
private static void process() {
Queue<Integer> queue = new LinkedList<>();
queue.add(startVertex);
while (!queue.isEmpty()) {
Integer vertex = queue.poll();
for (Integer nextVertex : adjacencyList[vertex]) {
if (distance[nextVertex] != 0) {
continue;
}
if (nextVertex == startVertex) {
continue;
}
distance[nextVertex] = distance[vertex] + 1;
queue.add(nextVertex);
}
}
for (int vertex = 1; vertex <= numberOfVertex; vertex++) {
if (distance[vertex] == targetDistance) {
result.add(vertex);
}
}
if (result.isEmpty()) {
result.add(-1);
}
Collections.sort(result);
}
private static void output() {
for (Integer vertex : result) {
System.out.println(vertex);
}
}
}Dijkstra
- 가중치가 없는 그래프에서는 굳이 Dijkstra를 사용할 필요 없을 듯
package shortest_path;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main_18352_dijkstra {
private static int numberOfCity;
private static int numberOfRoad;
private static int targetDistance;
private static int startCity;
private static int[] minDistance;
private static ArrayList<Integer> result = new ArrayList<>();
private static ArrayList<City>[] adjacencyList;
static class City {
int number;
int distance;
public City(int number, int distance) {
this.number = number;
this.distance = distance;
}
}
public static void main(String[] args) throws IOException {
input();
process();
output();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
numberOfCity = Integer.parseInt(st.nextToken());
numberOfRoad = Integer.parseInt(st.nextToken());
targetDistance = Integer.parseInt(st.nextToken());
startCity = Integer.parseInt(st.nextToken());
minDistance = new int[numberOfCity + 1];
adjacencyList = new ArrayList[numberOfCity + 1];
for (int i = 1; i <= numberOfCity; i++) {
adjacencyList[i] = new ArrayList<>();
}
for (int i = 0; i < numberOfRoad; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int destination = Integer.parseInt(st.nextToken());
adjacencyList[start].add(new City(destination, 1));
}
}
private static void process() {
dijkstra(startCity);
for (int city = 1; city <= numberOfCity; city++) {
if (minDistance[city] == targetDistance) {
result.add(city);
}
}
if (result.isEmpty()) {
result.add(-1);
}
}
private static void dijkstra(int startCity) {
Queue<City> queue = new PriorityQueue<>(Comparator.comparingInt(city -> city.distance));
initDistance();
queue.add(new City(startCity, 0));
while (!queue.isEmpty()) {
City city = queue.poll();
int cityNumber = city.number;
int cityDistance = city.distance;
if (cityDistance > minDistance[cityNumber]) {
continue;
}
for (City nextCity : adjacencyList[cityNumber]) {
int nextCityNumber = nextCity.number;
int newDistance = minDistance[cityNumber] + nextCity.distance;
if (newDistance >= minDistance[nextCityNumber]) {
continue;
}
minDistance[nextCityNumber] = newDistance;
queue.add(new City(nextCityNumber, newDistance));
}
}
}
private static void initDistance() {
for (int city = 1; city <= numberOfCity; city++) {
minDistance[city] = Integer.MAX_VALUE;
if (city == startCity) {
minDistance[city] = 0;
}
}
}
private static void output() {
result.forEach(System.out::println);
}
}