[백준] 18352 특정 거리의 도시 찾기 - 다익스트라알고리즘

문제

---

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

 

 

 

풀이

---

다익스트라 알고리즘을 통해서 출발 도시에서의 갈 수있는 도시의 최단거리를 모두 구해준뒤.

K 값과 같은 거리를 구해주면 된다.

 

아래의 코드가 다익스트라 알고리즘이다.

static void dijkstra(int x) {
	
	Queue<Integer> queue = new LinkedList<>();
	queue.add(x);		
	
	while(!queue.isEmpty()) {
		
		int top = queue.poll();
		
		for(int num : map[top]) {
			
			if(dist[num] != Integer.MAX_VALUE) {
				
				if(dist[num] >= dist[top] + 1) {
					dist[num] = dist[top] + 1;
					queue.add(num);
				}
				
			}
			else {
				dist[num] = dist[top] + 1;
				
				queue.add(num);
			}
		}
	}
}

 

이렇게 모든 경로를 찾아준 뒤에 해당 k 값과 같은 값들의 번호를 찾아주면 된다.

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static List<Integer>[] map;
	static int[] dist;
			
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		int n = parseInt(st.nextToken());
		map = new List[n + 1];
		for(int i = 1 ; i <= n; i++) {
			map[i] = new ArrayList<>();
		}
		
		dist = new int[n + 1];
		for(int i = 1; i <= n ; i++) {
			dist[i] = Integer.MAX_VALUE;
		}
		
		int m = parseInt(st.nextToken());
		int k = parseInt(st.nextToken());
		int x = parseInt(st.nextToken());
		
		
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			
			int start = parseInt(st.nextToken());
			int end = parseInt(st.nextToken());
			
			map[start].add(end);
		}
		
		dist[x] = 0;
		dijkstra(x);
		
		boolean isTrue = false;
		for(int i = 1 ; i <= n ;i++) {
			if(dist[i] == k) {
				sb.append(i + "\n");
				isTrue = true;
			}
		}
		
		if(!isTrue) {
			sb.append(-1);
		}
		
		
		System.out.println(sb);
	}
	
	static void dijkstra(int x) {
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(x);		
		
		while(!queue.isEmpty()) {
			
			int top = queue.poll();
			
			for(int num : map[top]) {
				
				if(dist[num] != Integer.MAX_VALUE) {
					
					if(dist[num] >= dist[top] + 1) {
						dist[num] = dist[top] + 1;
						queue.add(num);
					}
					
				}
				else {
					dist[num] = dist[top] + 1;
					
					queue.add(num);
				}
			}
			
		}
		
	}
	
}