[Algorithm] 특정 거리의 도시 찾기

문제

어떤 나라에 1~N번까지의 도시와 M개의 단방향 도로가 존재한다.

모든 도로의 거리는 1이다. 이때 X도시에서 출발하여 도달할 수 있는 도시 중 최단거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램 작성하시오. X 도시에서 X 도시까지의 거리는 0으로 가정한다.

 

입력 조건

첫째 줄에 N, M, K, X가 주어진다.

둘째 줄부터 A도시에서 B도시로 이동하는 단방향 도로 정보가 주어진다.

 

출력 조건

최단거리 K로 도달 할 수 있는 모든 도시를 오름차순으로 출력.

하나도 없다면 -1 출력

 

풀이

먼저 도로에 대한 정보가 주어지는 것을 인접리스트 방식으로 그래프화 시킨다.

도시별 최단거리를 저장할 배열을 선언한다.

처음 시작 도시 X의 거리를 0으로 지정하고, 나머지는 -1로 초기화 한다.

자료구조 큐에 X도시부터 넣고 인접한 도시들로 거리를 계산한다.

 

계산이 끝나면 K와 거리가 같은 도시들을 출력한다.

없을 경우 -1을 출력하도록 한다.

import java.util.*;


public class Main {

    public static int n, m, k, x;
    public static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    public static int[] d = new int[300001];

    public static void main(String[] args) {
        // 1 N 까지의 도시
        // M개 단방향 도로
        // X에서 출발해 최단거리가 정확히 K인 도시들의 번호 출력

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        x = sc.nextInt();

        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<Integer>());
            d[i] = -1;
        }

        for (int i = 0; i < m; i++) {
            int tmp = sc.nextInt();
            int tmp2 = sc.nextInt();
            list.get(tmp).add(tmp2);
        }
        sc.close();

        d[x] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(x);
        while(!q.isEmpty()) {
            int now = q.poll();
            for (int i = 0; i < list.get(now).size(); i++) {
                int next = list.get(now).get(i);
                if (d[next] == -1) {
                    d[next] = d[now] + 1;
                    q.offer(next);
                }
            }
        }

        boolean isEmpty = true;
        for (int i = 1; i <= n; i++) {
            if (d[i] == k) {
                System.out.println(i + " ");
                isEmpty = false;
            }
        }

        if (isEmpty) {
            System.out.println(-1);
        }
        

    }
}