[백준]BOJ 18352 특정 거리의 도시 찾기(자바/다익스트라/메모리초과 해결)

 

한 정점에서 다른 정점으로 가는 최단 거리의 문제입니다.  다음과 같이 모든 도로의 거리는 1이라는 조건이 있습니다. 이를 통해 BFS나 다익스트라로 문제를 풀어볼 수 있음을 알 수 있었습니다.

 

 

 

 

어려웠던 점

 

처음에는 인접행렬로 이 문제를 풀이했습니다. 제출했더니 메모리 초과가 났습니다.

 

 

이후에, 인접 리스트로 다시 문제를 풀었고, 다행히 성공할 수 있었습니다. 인접리스트로 단방향에 대해 저장하였습니다. 

 

 

 

---

 

 

 

구현

 

큐에는 정점들을 넣었고, 현재 정점에 대해 경유지로 삼는 인접한 정점들을 방문하고 갱신한 뒤 이 정점을 큐에 넣었습니다.

public class Main_18352 {
	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> result = new ArrayList<Integer>();
		ArrayList<Integer>[] citys = new ArrayList[N+1];
		
		for (int i = 1; i <= N; i++) {
			citys[i] = new ArrayList<Integer>();
		}
		
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			citys[a].add(b);// 단방향
		}
		

		boolean[] visited = new boolean[N + 1];
		int[] distance = new int[N + 1];

		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[X] = 0;// 출발 정점

		PriorityQueue<Integer> pq = new PriorityQueue<>();
		pq.add(X);
		
		while(!pq.isEmpty()) {
			int now = pq.poll();//현재 방문 정점
			
			for (int i = 0; i < citys[now].size(); i++) {//현재 정점을 경유지로 삼는 인접한 정점을 방문함
				if(distance[citys[now].get(i)] > distance[now] + 1) {
					distance[citys[now].get(i)] = distance[now] + 1;
					pq.add(citys[now].get(i));
				}
				
			}
			
		}
		
		//System.out.println(Arrays.toString(distance));
		
		for (int i = 1; i <= N; i++) {
			if(distance[i] == K) result.add(i);
		}
		
		if (result.size() == 0)
			System.out.println(-1);
		else {
			Collections.sort(result);
			for (int i = 0; i < result.size(); i++) {
				System.out.println(result.get(i));
			}
		}

	}
}