이코테 - 특정 거리의 도시 찾기 with JAVA

 

 

 

 

 

 

1. 입력받을 때는 아래와 같이 nextInt() 써서 입력받자

2. List<Integer> queue = new ArrayList<>(); 보다 Queue<Integer> queue = new LinkedList<>();가 효율적이다.

-> 전자는 삭제시 모든 데이터를 앞으로 땡기기위해 옮겨야 하지만 후자는 그렇지 않기 때문이다.

3. 단방향이기에 방문처리가 필요없다.

 

 

import java.util.*;

public class Q1 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int x = sc.nextInt();

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

        for (int i=0; i<m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            map.get(from).add(to);
        }

        distance[x] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        while (queue.size() > 0) {
            int now = queue.poll();
            for(int next : map.get(now)){
                if (distance[next] == -1) {
                    distance[next] = distance[now]+1;
                    queue.add(next);
                }
            }
        }

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

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