99클럽 코테 스터디 10일차 TIL (18352번: 특정 거리의 도시 찾기)

문제

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

---

학습 키워드

• BFS

 

시도

• 출발 도시부터 시작해서 연결되있는 가까운 도시를 탐색한다. 탐색하면서 이동한 거리를 저장하고, 만약 이동한 거리가 주어진 K와 같다면 정답에 추가한다.

 

풀이 및 코드

• List<Integer> listAnswer : 거리 정보 K와 거리가 같은 도시의 목록
• Map<Integer, List<Integer>> graph : 도시간 연결을 Map으로 표시했다. 
  • 예제 입력 1을 기준으로 1: {2, 3}, 2: {3, 4}와 같이 저장된다.
• boolean[] visited : 해당 도시를 이미 탐색했는지 판단하기 위한 배열
• int[] distance : 출발 도시 X부터의 거리를 저장하기 위한 배열

 

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

public class Main18352 {

	private static List<Integer> listAnswer = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(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());

		Map<Integer, List<Integer>> graph = new HashMap();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
		}

		boolean[] visited = new boolean[N + 1];
		int[] distance = new int[N + 1];
		bfs(graph, visited, distance, X, K);
		if (listAnswer.size() == 0) {
			System.out.println(-1);
		} else {
			Collections.sort(listAnswer);
			for (int cityNumber : listAnswer) {
				System.out.println(cityNumber);
			}
		}
	}

	private static void bfs(Map<Integer, List<Integer>> graph, boolean[] visited, int[] distance, int X, int K) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(X);
		visited[X] = true;

		while (!queue.isEmpty()) {
			int current = queue.poll();
			if (distance[current] == K) {
				listAnswer.add(current);
			}
			if (!graph.containsKey(current)) {
				continue;
			}
			for (int to : graph.get(current)) {
				if (visited[to]) {
					continue;
				}
				visited[to] = true;
				distance[to] = distance[current] + 1;
				queue.offer(to);
			}
		}
	}
}