[java] 백준 18352 : 특정 거리의 도시찾기

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

풀이

visited배열을 생성하여 이전 도시의 기록과 합하여 도시에 방문한 횟수를 기록합니다.

특정 거리에 해당하는 visited idx를 출력합니다

 

import java.util.*;

public class Main {
	static ArrayList<Integer>[] arr;
	static ArrayList<Integer> answer;
	static int[] visited;
	static int N;
	static int M;
	static int K;
	static int X;
	static int count=0;
	

	public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);
	
	N = sc.nextInt(); //도시의 개수
	M = sc.nextInt(); //도로의 개수
	K = sc.nextInt(); //거리정보
	X = sc.nextInt(); //출발 도시의 번호
	
	
	arr= new ArrayList[N+1];
	answer = new ArrayList<Integer>();
	
	//노드 수 만큼
	for(int i=1; i<=N ;i++) {
		arr[i] = new ArrayList<Integer>();
		}
	
	
	for(int i=0; i<M ;i++) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		arr[a].add(b);
		}
	
	
	visited = new int[N+1];
	for(int i=1; i<=N ;i++) {
		visited[i] = -1;
		}
	
	BFS();
	ArrayList<Integer> an = new ArrayList<Integer>();
	for(int i=1; i<=N ;i++) {
		if(visited[i]==K) {
			count++;
			an.add(i);
		}
		}
	
	if(count==0)System.out.println(-1);
	Collections.sort(an);
	for(int a: an) {
		System.out.println(a);
	}

	}

	static public void BFS() {
		Queue<Integer> q = new LinkedList<>();
		q.add(X);
		visited[X]++;
		while(!q.isEmpty()) {
			int n = q.poll();
			for( int y:arr[n]) {
				if(visited[y]==-1) {

					q.add(y);
					visited[y] = visited[n]+1;
				}
				}
		}
		
		
	}

}