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

🔗 문제 링크

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

😮 문제 해결 방법

문제의 조건에서 최대 300,000개의 도시가 입력으로 주어질 수 있다고 명시했기 때문에, 인접행렬 방식이 아닌 인접 리스트 방식으로 해결해야한다.

시작 도시부터 도달할 수 있는 모든 도시에 대해 최단거리를 구하는 알고리즘은 “다익스트라"를 사용할 수 있다.

물론, 해당 문제에서도 다익스트라 알고리즘을 사용할 수 있지만, 각 도시간 거리가 1로 고정이 되어있기 때문에 BFS를 이용해서도 문제를 해결할 수 있다.

1. 출발 도시를 시작으로 BFS를 구현한다.
2. 연결된 도시 중 방문하지 않고, 현재 도시에서 거리에 +1 한 값보다 연결된 도시 거리가 멀다면 최단 거리로 갱신한다.
3. 시작 도시로 부터 도달할 수 있는 도시의 최단 거리를 모두 구한 뒤 K랑 거리가 같은 도시를 리스트에 담는다.
4. 리스트 사이즈가 0이라면, K 거리로 도달할 수 있는 도시가 없는 경우 이므로 -1을 리턴한다.
5. 그 외의 경우 리스트를 오름차순 정렬을 한뒤 리턴한다.

출력 조건으로 BufferedWriter를 사용하지 않는 경우 50%에서 출력 초과가 발생했다.

🚩 Java 코드

package com.algorithm.Baekjoon;

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

public class Main_18352_특정_거리의_도시_찾기 {
    private static List<List<Integer>> graph;
    private static final int INF = (int) 1e9;

    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());       // 도시 (vertex)
        int M = Integer.parseInt(st.nextToken());       // 도로 (edge)
        int K = Integer.parseInt(st.nextToken());       // 도달 거리
        int X = Integer.parseInt(st.nextToken());       // 시작 도시

        // 그래프 초기화
        graph = new ArrayList<>();
        for (int vertex = 0; vertex <= N; vertex++) {
            graph.add(new ArrayList<>());
        }

        // 도로 연결
        for (int edge = 0; edge < M; edge++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(end);
        }

        int[] rst = getMinDistanceCity(N, K, X);

        // BufferedWriter 안쓰면 출력 초과 에러
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int city : rst) {
            bw.write(String.valueOf(city));
            bw.newLine();
        }
        bw.flush();
        br.close();
    }

    private static int[] getMinDistanceCity(int n, int k, int x) {
        Queue<Integer> pq = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        int[] distance = new int[n + 1];
        Arrays.fill(distance, INF);

        pq.add(x);
        distance[x] = 0;        // 시작도시 거리 0
        visited[x] = true;      // 시작도시 방문 처리

        while (!pq.isEmpty()) {
            int city = pq.poll();
            for (int next : graph.get(city)) {
                // 거리 비교해서 최단 거리인 경우 갱신
                if (!visited[next] && distance[next] > distance[city] + 1) {
                    visited[next] = true;
                    distance[next] = distance[city] + 1;
                    pq.add(next);
                }
            }
        }

        // X 도시에서 도달할 수 있는 최단 거리 중 K인 도시 구하기
        List<Integer> rst = new ArrayList<>();
        for (int city = 1; city <= n; city++) {
            if (distance[city] == k) rst.add(city);
        }

        // K인 도시 없으면 return 0
        if (rst.size() < 1) return new int[]{-1};

        // 도시 오름차순 정렬 후 리턴
        Collections.sort(rst);
        return rst.stream().mapToInt(Integer::intValue).toArray();
    }
}