백준 - 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이기 때문에 출력하지 않는다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static class Node implements Comparable<Node> {

        int num;    // 노드 번호
        int weight; // 해당 노드까지의 거리

        public Node(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }

    }

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());    // 도시의 개수
        int M = Integer.parseInt(tokenizer.nextToken());    // 도로의 개수
        int K = Integer.parseInt(tokenizer.nextToken());    // 거리 정보
        int X = Integer.parseInt(tokenizer.nextToken());    // 출발 도시 번호

        List<Node>[] adjList = new List[N + 1];
        for (int i = 0; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int from = Integer.parseInt(tokenizer.nextToken()); // 시작
            int to = Integer.parseInt(tokenizer.nextToken());   // 끝

            adjList[from].add(new Node(to, 1));  // 단방향 그래프
        }

        // 다익스트라 -> 방문 체크(확정 여부), 거리 배열 필요

        boolean[] isVisited = new boolean[N + 1];   // 방문 체크
        int[] weights = new int[N + 1]; // X로부터의 거리
        Arrays.fill(weights, Integer.MAX_VALUE);
        weights[X] = 0; // 출발지 처리. 자기 자신으로의 거리는 0

        Queue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(X, 0)); // 출발 정점 번호

        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            if (isVisited[curr.num]) continue;

            isVisited[curr.num] = true;
            weights[curr.num] = curr.weight;

            for (Node node : adjList[curr.num]) {
                if (!isVisited[node.num] && weights[node.num] > weights[curr.num] + node.weight) {
                    weights[node.num] = weights[curr.num] + node.weight;
                    queue.offer(new Node(node.num, weights[node.num]));
                }
            }
        }
        
        for (int i = 1; i <= N; i++) {
            if (weights[i] == K) sb.append(i).append("\n");
        }

        System.out.println(sb.length() == 0 ? "-1" : sb);
    }

}

• 다익스트라를 이용해 풀었다.
• 메모리와 실행시간이 생각보다 많이 나와서 놀랐다. 틀린 부분은 없는 것 같은데 코드를 다시 한번 봐야 할 것 같다.