[Algorithm /백준] 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을 출력한다.


[문제 해결 - 다익스트라]

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	static int[] distance;
	static ArrayList<ArrayList<Integer>> graph;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int INF = Integer.MAX_VALUE/4;
        int N = sc.nextInt(); // 도시의 갯수
        int M = sc.nextInt(); // 도로의 갯수
        int K = sc.nextInt(); // 거리정보 K
        int X = sc.nextInt(); // 출발도시 X
        
        distance = new int[N+1];
        graph = new ArrayList<>();
        
        for(int i = 0 ; i <= N ; i++) {
        	graph.add(new ArrayList<>());
        }
        
        for(int i = 0 ; i < distance.length; i++) {
        	distance[i] = INF;
        }
        
        for(int i = 0; i < M; i++) {
        	int num1 = sc.nextInt();
        	int num2 = sc.nextInt();
        	graph.get(num1).add(num2);
        }
        
        //출발도시 X의 거리정보 초기화
        distance[X] = 0;
        
        //다이스트라 알고리즘 실행
        dijkstra(X);
        
        int cnt = 0;
        
        //만약 K위치의 거리에 있는게 있다면 순서대로 출력.
        for(int i = 1; i <distance.length ; i++) {
        	if(distance[i] == K) {
        		System.out.println(i);
        		cnt++;
        	}
        }
        
        //만약 하나도 없다면 -1 출력
        if(cnt == 0) System.out.println(-1);

        
    }
    public static void dijkstra(int start) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        // 우선순위 큐에 시작 노드를 추가
        q.add(start);

        while (!q.isEmpty()) {
         // 현재 노드를 우선순위 큐에서 꺼냄
            int current = q.poll();

            for (int j = 0; j < graph.get(current).size(); j++) {
             // 현재 노드를 거쳐서 인접한 노드로 이동하는 데 걸리는 비용
                int cost = distance[current] + 1;

                // 다음 노드로 이동하는 경우에 현재까지의 비용과 비교하여 더 작은 비용이면 갱신하고 우선순위 큐에 추가
                if (cost < distance[graph.get(current).get(j)]) {
                // 최단 거리 갱신
                    distance[graph.get(current).get(j)] = cost; 
                    // 다음 노드를 우선순위 큐에 추가하여 탐색 계속
                    q.add(graph.get(current).get(j)); 
                }
            }
        }
    }

}

 

 

 

+) 개념을 이해하기는 했어도 막상 코드로 짜려니 막막했던 다익스트라 알고리즘!

 

기본구조를 여러번 반복해야겠다는 생각이 들었다.