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

문제

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

 

접근 방식

노드 간의 거리가 모두 1로 동일할 때, 시작점 X에서 거리가 K인 정점을 출력해야 한다.

 

즉 탐색은 X에서 K번 까지의 이동만 진행해주면 되고, K번째 방문한 정점들을 모두 저장해주면 되는데

문제에서 요구하는 출력값이 정점의 번호를 오름차순으로 출력하는 것이기 때문에

트리셋이나 우선순위큐, 정렬 등을 사용해서 출력해주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());

		int[] isVisited = new int[n + 1];
		Arrays.fill(isVisited, -1);

		ArrayList<ArrayList<Integer>> near = new ArrayList<>();
		TreeSet<Integer> result = new TreeSet<>();

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			near.get(a).add(b);
		}

		Queue<Integer> q = new ArrayDeque<>();

		q.offer(x);
		isVisited[x] = 0;

		while (!q.isEmpty()) {
			int cur = q.poll();

			for (int next : near.get(cur)) {
				if (isVisited[next] != -1) continue;
				isVisited[next] = isVisited[cur] + 1;
				if (isVisited[next] == k) {
					result.add(next);
					continue;
				} else if (isVisited[next] > k) {
					continue;
				}
				q.offer(next);
			}
		}

		if (result.isEmpty()) {
			sb.append(-1);
		} else {
			for (int i : result) {
				sb.append(i).append("\n");
			}
		}

		System.out.println(sb);
	}
}