BOJ18352 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352 (opens new window)

어떤 나라에는 1번 부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성한다. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

Node.java

정점과 거리를 관리하기 위한 Node 클래스이다.

private static class Node {
    private int index;
    private int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }
}

dijkstra

최단 경로를 탐색하기 위한 dijkstra 메소드이다.

PriorityQueue는 거리의 우선순위가 가장 작은 것 부터 꺼내올 수 있도록 설정하였다.

private static void dijkstra(int start) {
    PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));

    priorityQueue.offer(new Node(start, 0));
    d[start] = 0;

    while (!priorityQueue.isEmpty()) {

        Node currentNode = priorityQueue.poll();
        int index = currentNode.index;
        int distance = currentNode.distance;

        if (d[index] < distance) {
            continue;
        }

        for (int i = 0; i < graph.get(index).size(); i++) {
            int cost = d[index] + graph.get(index).get(i).distance;
            if (cost < d[graph.get(index).get(i).index]) {
                d[graph.get(index).get(i).index] = cost;
                priorityQueue.offer(new Node(graph.get(index).get(i).index, cost));
            }
        }
    }
}

제출 코드

위에서 작성한 dijkstra 메소드를 활용하여 특정 정점 부터의 최단 거리를 배열에 저장한다.

모든 최단 거리를 순회하여 정확히 K인 도시를 출력하여 마무리한다.

아래는 최종 제출 코드이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class BOJ18352 {

    private static final int INF = Integer.MAX_VALUE;
    private static List<List<Node>> graph = new ArrayList<>();
    private static int[] d = new int[300_001];

    private static class Node {
        private int index;
        private int distance;

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }
    }

    private static void dijkstra(int start) {
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));

        priorityQueue.offer(new Node(start, 0));
        d[start] = 0;

        while (!priorityQueue.isEmpty()) {

            Node currentNode = priorityQueue.poll();
            int index = currentNode.index;
            int distance = currentNode.distance;

            if (d[index] < distance) {
                continue;
            }

            for (int i = 0; i < graph.get(index).size(); i++) {
                int cost = d[index] + graph.get(index).get(i).distance;
                if (cost < d[graph.get(index).get(i).index]) {
                    d[graph.get(index).get(i).index] = cost;
                    priorityQueue.offer(new Node(graph.get(index).get(i).index, cost));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 도시(노드)의 개수
        int m = scanner.nextInt(); // 도로(간선)의 개수
        int k = scanner.nextInt(); // 거리 정보
        int x = scanner.nextInt(); // 출발 도시의 번호

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            graph.get(a).add(new Node(b, 1));
        }

        Arrays.fill(d, INF);

        dijkstra(x);

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (d[i] == k) {
                stringBuilder.append(i).append("\n");
            }
        }

        if (stringBuilder.toString().isBlank()) {
            System.out.println("-1");
            return;
        }

        System.out.println(stringBuilder);
    }
}

#algorithm #BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #다익스트라 #BFS