[BOJ] 18352: 특정 거리의 도시 찾기 (JAVA)

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

 

풀이

 

BFS로 문제를 풀었는데, 시간초과가 발생했다.

시간초과 해결에 결정적인 도움을 준 생각이 아래의 생각이다.

만약, 도시가 300,000개 있을 때, 
1 -> 2 -> 3 -> ... -> 300,000 까지 이어진 단방향 도로가 있다.

시작 도시가 2 이고, 거리가 2인 도시를 구해야 할 경우 정답은 4밖에 없다.
근데 이럴 경우 내가 300,000 번째 도시까지 가야할 이유가 있을까?

 

BFS로 찾아주다가, 내가 찾아야 하는 K를 초과하는 경우 return문으로 빠져나왔다.

다익스트라로 문제를 풀면 더 빠르게 구할 수 있을 것 같다.

 

package 백준renew;

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

public class 실버2_18352_특정거리의도시찾기 {
	static int N, M, K, X;
	static int map[][];
	static int city[];
	static boolean visited[];
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		
		StringTokenizer 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());
		
		city = new int[N+1];
		map = new int[M][2];
		visited = new boolean[N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			map[i][0] = Integer.parseInt(st.nextToken());
			map[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Search(X);
		
		city[X] = 0;
		
		Count();
		
		if(sb.length() == 0) {
			sb.append(-1);
		}
		
		bw.write(sb.toString());
		bw.close();
	}
	static void Search(int start) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		
		while(!q.isEmpty()) {
			int now = q.poll();
			for(int i=0; i<M; i++) {
				if(map[i][0]==now && !visited[map[i][1]]) {
					city[map[i][1]] = city[now]+1;
					if(city[map[i][1]] > K) {
						return;
					}
					q.offer(map[i][1]);
					visited[map[i][1]] = true;
				}else {
					continue;
				}
			}
		}
	}
	static void Count() {
		for(int i=1; i<=N; i++) {
			if(city[i]==K) {
				sb.append(i).append('\n');
			}
		}
	}
}