[백준 18352] 특정 거리의 도시 찾기 in JAVA

www.acmicpc.net/problem/18352

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

문제 | 정점 X로부터의 최단 거리가 K인 정점 찾기

 

 

※ 풀이 방법

 BFS를 사용하여 해결하였다.

 BFS를 통하여 각 정점별 최단거리를 저장하고 최단거리가 K인 경우에 출력해주었다.

 최단거리가 K인 도시의 개수도 따로 체크해서 최단 거리가 K인 도시가 없을 경우에는 -1을 출력해주었다.

 

※ 문제 풀이 코드

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

public class BOJ_18352 {
	public static ArrayList<Integer> [] graph;
	public static int [] path;
	public static LinkedList<Integer> queue;
	
	public static void bfs(int X) {
		queue.addLast(X);
		int a,b;
		while(!queue.isEmpty()) {//큐가 빌 때까지(모든 노드를 방문할 때까지) 수행
			a=queue.removeFirst();
			for(int i=0;i<graph[a].size();i++) {
				b=graph[a].get(i);
				if(path[b]==0) {//방문한 적 없는 노드일 경우
					path[b]+=path[a]+1;
					queue.add(b);
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		String s=br.readLine();
		st=new StringTokenizer(s);
		
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int K=Integer.parseInt(st.nextToken());
		int X=Integer.parseInt(st.nextToken());
		
		graph=new ArrayList[N+1];
		path=new int[N+1];
		queue=new LinkedList<Integer>();
		
		for(int i=1;i<=N;i++)
			graph[i]=new ArrayList<Integer>();
		
		int a,b;
		
		for(int i=0;i<M;i++) {
			s=br.readLine();
			st=new StringTokenizer(s);
			a=Integer.parseInt(st.nextToken());
			b=Integer.parseInt(st.nextToken());
			graph[a].add(b);
		}
		
		bfs(X);
		
		int cnt=0;
		
		for(int i=1;i<=N;i++) {
			if(path[i]==K&&i!=X) {
				System.out.println(i);
				cnt++;
			}
		}
		if(cnt==0) System.out.println(-1);//최단거리가 K인 노드가 하나도 없을 경우
	}

}