특정거리의 도시찾기

이 문제는 최단거리를 찾아내는 과정을 BFS알고리즘을 통해 해결할 수 있습니다.
알고리즘 개략적인 부분은 아래와 같습니다.

1. pq에 시작위치와 depth를 저장
2. ans를 위한 pq선언
3. BFS
   1. depth가 우리가 찾는 depth라면 ans 에 node번호를 넣기(2의 pq에서 첫번째 요소) 그리고 continue
   2. 그게 아니라면 2의 pq 전체를 돌면서 현재 node의 사이즈만큼 돈다. next를 선언
      1. 방문하지 않았다면 방문체크해주고 pq에 넣어준다. next, cost+1 로
4. ans 의 사이즈가 0 이면 -1 그렇지않으면 ans 가 empty가 아닐때까지 poll 해서 정답을 유추한다.

package programmers;

import java.util.*;
import java.io.*;
public class 프로그래머스_특정거리의도시찾기2  {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //도시 개수 
		int M = Integer.parseInt(st.nextToken()); //도로의 개수
		int K = Integer.parseInt(st.nextToken()); //거리 정보
		int X = Integer.parseInt(st.nextToken()); //출발 도시의 번호
		
		ArrayList<Integer>[] map = (ArrayList<Integer>[])new ArrayList[N+1];
		int[] visit = new int[N+1];
		for(int i=1; i<=N; i++) {
			map[i] = new ArrayList<>();
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int f=Integer.parseInt(st.nextToken());
			int s=Integer.parseInt(st.nextToken());
			map[f].add(s);
		}
		
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		visit[X] = 1;
		pq.add(new int[] {X,0});
		PriorityQueue<Integer> ans = new PriorityQueue<>();
		while(!pq.isEmpty()) {
			int[] k = pq.poll();
			int Edge = k[0];
			int depth = k[1];
			
			if(depth == K) {
				ans.add(Edge);
				continue;
			}
			
			for(int i=0; i<map[Edge].size(); i++) {
				int next = map[Edge].get(i);
				if(visit[next]==0) {
					visit[next] = 1;
					pq.add(new int[] {next, depth+1});
				}
			}//end of for loop
		}
		if(ans.size()==0)
			System.out.println("-1");
		else {
			while(!ans.isEmpty())
				System.out.println(ans.poll());
		}
	}
}