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

🔗 문제 링크

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

🔍 문제 설명

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

⚠️ 제한사항

• 2 ≤ N ≤ 300,000

• 1 ≤ M ≤ 1,000,000

• 1 ≤ K ≤ 300,000

• 1 ≤ X ≤ N

• 1 ≤ A, B ≤ N

---

🗝 풀이 (언어 : Java)

처음에는 인접 도시 정보를 이차원 배열로 담아서 풀었는데, 메모리 초과가 났다. 30만 * 30만 크기라 초과처리된 것 같다. 배열 안에 리스트로 인접 도시 정보를 가지도록 수정했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

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(), " ");
		int N = Integer.parseInt(st.nextToken()); //도시의 개수
		int M = Integer.parseInt(st.nextToken()); //도로의 개수
		int K = Integer.parseInt(st.nextToken()); //타겟 거리 정보
		int X = Integer.parseInt(st.nextToken()); //출발 도시
		List<Integer>[] edges = new ArrayList[N + 1];
		for (int i = 0; i < edges.length; i++) {
			edges[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st2.nextToken());
			int end = Integer.parseInt(st2.nextToken());
			edges[start].add(end);
		}
		br.close();
		solution(X, K, edges);
	}

	private static void solution(int start, int distance, List<Integer>[] edges) {
		List<Integer> answer = new ArrayList<>();
		boolean[] visited = new boolean[edges.length];
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		visited[start] = true;
		int currentDistance = -1;
		while (!queue.isEmpty()) {
			currentDistance++;
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int city = queue.poll();
				if (currentDistance == distance) {
					answer.add(city);
					continue;
				}
				for (Integer nextCity : edges[city]) {
					if (!visited[nextCity]) {
						visited[nextCity] = true;
						queue.add(nextCity);
					}
				}
			}
		}
		if (answer.isEmpty()) {
			answer.add(-1);
		}
		answer.stream().sorted().forEach(System.out::println);
	}

}