[JAVA] 백준 18352_특정 거리의 도시 찾기

[문제링크]

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

 

📌 문제 탐색하기

어떤 나라에 N개의 도시와 M개의 거리가 1인 단방향 도로가 있다.
출발 도시 X에서 최단 거리가 정확히 K인 모든 도시를 찾아 오름차순으로 출력하는 문제이다.
만약 존재하지 않으면 -1을 출력

📌코드 설계하기

1. 입력 받기
2. 그래프 저장 
3. BFS로 최단 거리 계산
4. 거리 K인 도시 찾기
5. 결과 출력하기
(오름차순 정렬 후 출력 /  없으면 -1)

📌 가능한 시간복잡도

BFS의 시간복잡도는 모든 도로를 각각 한번씩 탐색하기 때문에
가능한 시간복잡도는 O(N+M)입니다.

📌 정답 코드

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

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<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            graph.get(A).add(B);
        }
        
        int[] distance = new int[N + 1];
        Arrays.fill(distance, -1);
        distance[X] = 0; 
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(X);
        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int next : graph.get(current)) {
                if (distance[next] == -1) {
                  
                    distance[next] = distance[current] + 1;
                    queue.offer(next);
                }
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            if (distance[i] == K) {
                result.add(i);
            }
        }

        if (result.isEmpty()) {
            System.out.println(-1);
        } else {
            Collections.sort(result);
            for (int city : result) {
                System.out.println(city);
            }
        }
    }
}