백준 No.18352특정 거리의 도시 찾기 - JAVA

문제

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

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

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

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

 

 

풀이

- 방향성 그래프, 거리를 구한다 --> 다익스트라

-  출발점부터 시작하여 dist 배열에다가 1씩 추가하면 된다.

-  그러고 dist 배열 값 중에 K와 일치하는 값이 있다면 출력 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {


    static int dist[];
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        boolean result = false;

        int N = Integer.parseInt(st.nextToken());   //도시의 개수
        int M = Integer.parseInt(st.nextToken());   //도록의 개수
        int K = Integer.parseInt(st.nextToken());   // 거리 정보
        int X = Integer.parseInt(st.nextToken());   //시작

        for (int i = 0; i <= N ; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M ; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(new Node(end,1));
        }
        dist = new int[N+1];

        Arrays.fill(dist,Integer.MAX_VALUE);
        solution(X);

        for (int i = 0; i <= N; i++) {
            if(dist[i] != Integer.MAX_VALUE && dist[i] == K){
                sb.append(i).append("\n");
                result = true;
            }
        }

        if(result){
            System.out.println(sb);
        }else{
            System.out.println("-1");
        }
    }

    private static void solution(int k) {
        PriorityQueue<Node> queue = new PriorityQueue<>(((o1, o2) -> o1.cost - o2.cost));
        queue.add(new Node(k,0));
        dist[k] = 0;

        while (!queue.isEmpty()){
                Node now = queue.poll();

                for(Node next : graph.get(now.v)){
                    if(dist[next.v] > dist[now.v] + next.cost){
                        dist[next.v] = dist[now.v] + next.cost;
                        queue.add(new Node(next.v, dist[next.v]));
                    }
                }
        }
    }

    static class Node{
        int v;
        int cost;

        public Node(int v,int cost){
            this.v = v;
            this.cost= cost;
        }
    }
}