[백준_18352] 특정 거리의 도시 찾기

문제

백준 18352번
https://www.acmicpc.net/problem/18352

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

• 예시
  
  • ex1)에서 각 노드의 거리 정보를 보면 2는 1, 3은 1, 4는 2로 거리 정보 K = 2인 곳인 결과 4가 나온다.
  • ex2)에서 각 노드의 거리 정보를 보면 2, 3, 4 전부 1로 거리 정보 K = 2와 일치하는 곳이 없어 -1이라는 결과가 나온다.

Code

보통 다익스트라를 풀 때 각 노드마다 가중치가 다르지만, 현재 문제에서는 모든 노드의 가중치는 1로 통일해서 풀 수 있다. 다익스트라의 완전 기초적인 문제라고 판단된다.

Java

import java.util.*;

public class Main {
    // 다음 노드값과 가중치
    static class Node {
        int to;
        int weight;

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

    public static void dijkstra(int N, int[][] data, int K, int X) {
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();

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

        for (int i = 0; i < data.length; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], 1));
        }

        int[] dist = new int[N + 1];
        for (int i = 1; i < N + 1; i++) { // dist 값을 최댓값으로 초기화
            dist[i] = Integer.MAX_VALUE;
        }
        dist[X] = 0; // 시작값은 0으로 초기화

        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.offer(new Node(X, 0));  // 시작 노드

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();

            for (int i = 0; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);

                if (dist[adjNode.to] > curNode.weight + adjNode.weight) { 
                // dist값이 현재 노드 weight + 이동할 노드 weight 값보다 큰지 작은지
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    pq.offer(new Node(adjNode.to, dist[adjNode.to]));
                }
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < dist.length; i++) {
            if (dist[i] == K) {
                result.add(i);
            }
        }

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

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int X = sc.nextInt();

        int[][] data = new int[M][2];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < 2; j++) {
                data[i][j] = sc.nextInt();
            }
        }

        dijkstra(N, data, K, X);
    }
}

• arraylist로 graph를 만들어 data에서 0번째 인덱스(from)를 넣고 동일한 인덱스에 해당하는 1번째 인덱스와 weight값인 1을 arraylist로 넣어준다.
• dist(거리) 배열을 만들어 전부 Integer.MAX_VALUE 값으로 초기화하고 우리가 시작하는 값인 X에 대해서만 0으로 초기화 시켜준다.
• 그리고 우선순위 큐를 통해 from.weight + to.weight < dist[to] 이 더 크다면 더 작은 값인 from.weight + to.weight값을 넣어주고 우선순위 큐에 해당 to값과 dist[to]를 넣어준다.
• 이를 반복해 거리 정보인 K와 일치하는 것은 result에 넣어주고 만약 result가 비어있다면 -1을 비어있지 않다면 for문을 통해 결과를 출력한다.