046 : 특정 거리의 도시 찾기

 

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
도시 X에서 최단거리가 K인 모든 도시 번호를 출력하시오		I // 도시수 N, 도로 수 M, 거리 K, 출발도시 X 1 : A B(A > B 도로) .. M : X Y(X > Y 도로)  O // 오름차순의 도시 번호 (없으면 -1)

 

import java.util.*;

public class Main {

    // Preprocessing
    static int visited[];
    static ArrayList<Integer>[] A;
    static int N, M, K, X;
    static List<Integer> answer;

    public static void main(String[] args) {

        // Input Supply Cable
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        X = sc.nextInt();

        // Preprocessing
        A = new ArrayList[N+1];
        answer = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < M; i++) {
            int S = sc.nextInt();
            int E = sc.nextInt();
            A[S].add(E);
        }
        visited = new int[N+1];
        for (int i = 0; i < N; i++) {
            visited[i] = -1;
        }

        // Operating BFS
        BFS(X);
        for (int i = 0; i <= N; i++) {
            if (visited[i] == K) {
                answer.add(i);
            }
        }

        // Output Extracting Cable
        if (answer.isEmpty()) {
            System.out.println("-1");
        } else {
            Collections.sort(answer);
            for (int temp : answer) {
                System.out.println(temp);
            }
        }
    }

    // External Module BFS
    private static void BFS(int Node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(Node);
        visited[Node]++;
        while (!queue.isEmpty()) {
            int now_Node = queue.poll();
            for (int i : A[now_Node]) {
                if (visited[i] == -1) {
                    visited[i] = visited[now_Node] + 1;
                    queue.add(i);
                }
            }
        }
    }
}