[BOJ 18352] 특정 거리의 도시찾기

문제

• BOJ 18352
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

1.입력이 간선정보로 들어오므로 각 번호마다 간선 정보를 저장해줄 Node클래스를 만들어서 각 노드의 간선 정보를 관리할 배열 nums를 생성한다.
2.모든 노드의 가중치가 1이므로 출발점부터 bfs로 탐색하면서 같은 거리에 있는 노드들은 큐에 넣어준다. 이렇게 큐에서 꺼낼때 마다 현재까지 온 거리를 체크해서 만약 찾고자 하는 K랑 같으면 ans리스트에 넣어주고 탐색을 종료한다.

import java.io.*;
import java.util.*;

//특정 거리의 도시 찾기
class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N,M,K,X; //도시, 간선, 최단거리, 출발번호
	static Node[] nums; //번호 리스트
	static boolean[] visited; //방문 체크
	static Queue<Node> q;
	static List<Integer> ans;
	
	static class Node{
		int num;
		List<Integer> nexts; //인접 리스트
		
		public Node(int num){
			this.num = num;
			nexts = new ArrayList<>();
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		
		//1번부터 시작
		nums = new Node[N+1];
		visited = new boolean[N+1];
		ans = new ArrayList<>();
		
		for(int i=1; i<=N; i++) nums[i] = new Node(i);
		
		for(int m=0; m<M; m++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int next = Integer.parseInt(st.nextToken());
			nums[num].nexts.add(next);
		}//End input
		
		q = new LinkedList<Node>();
		q.add(nums[X]); //출발노드: X
		visited[X] = true;
		
		int k = 1;
		while(!q.isEmpty()) {
			int size = q.size();
			for(int s=0; s<size; s++) {
				Node now = q.poll();
				
				if(now.nexts == null) continue; //간선정보가 없는 노드는 패스
				for(int i=0; i<now.nexts.size(); i++) {
					int next = now.nexts.get(i);
					
					if(!visited[next]) { //아직 방문안한 노드
						if(k == K) ans.add(next); //찾고자 하는 최단거리이면 답
						visited[next] = true; //방문처리
						q.add(nums[next]);
					}
				}
			}
			if(k == K) break; //다 찾았으면 종료
			k++;
		}//End search
		
		Collections.sort(ans); //순서대로 정렬
		if ( ans.size() == 0 ) System.out.println(-1);
		else for(int a : ans) System.out.println(a);
	}
}