[Algorithm] Dijkstra 특정 거리의 도시 찾기 (백준) - 에이젠

 

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

18352번: 특정 거리의 도시 찾기

공략

다익스트라 알고리즘 문제 입니다. 

정답률은 28퍼센트로 낮아보이네요.

하지만 그동안 풀었던 다익스트라 문제유형과 거의 똑같아서 쉽게 풀 수 있었습니다.

특정거리 K 번째의 dist요소들을 찾아서 출력하면 되겠습니다.

 

 

import java.util.*;

public class Main {

  static Scanner sc = new Scanner(System.in);

  static class Info {
    int idx;
    int distance;

    Info(int _idx, int _distance) {
      idx = _idx;
      distance = _distance;
    }

  }

  static class Edge {
    int to;
    int distance;

    Edge(int _to, int _distance) {

      to = _to;
      distance = _distance;

    }
  }

  static int N; // 도시 개수
  static int M; // 도로 개수
  static int K; // 찾아낼 도시의 거리
  static int X; // 출발 도시

  static int[] dist; // 각 도시까지의 거리
  static ArrayList<Edge>[] edges; // 인접 노드 리스트

  /**
   * 
   */
  static void input() {
    N = sc.nextInt();
    M = sc.nextInt();
    K = sc.nextInt();
    X = sc.nextInt();

    edges = new ArrayList[N + 1];
    dist = new int[N + 1];

    for (int i = 1; i <= N; i++) {
      edges[i] = new ArrayList<Edge>();
    }

    for (int i = 1; i <= M; i++) {
      int from = sc.nextInt();
      int to = sc.nextInt();

      edges[from].add(new Edge(to, 1)); // 모든 도로의 거리가 동일하므로 1로 설정.
    }

  }

  static void dijkstra() {

    for (int i = 1; i <= N; i++) {
      dist[i] = Integer.MAX_VALUE;
    }

    PriorityQueue<Info> heap = new PriorityQueue<>(Comparator.comparing(o -> o.distance));

    // 시작점 세팅
    dist[X] = 0;
    heap.add(new Info(X, 0));

    while (!heap.isEmpty()) {
      Info info = heap.poll();
      // 필요없는 정보 거르기
      if (dist[info.idx] != info.distance) {
        continue;
      }

      for (Edge e : edges[info.idx]) {
        if (info.distance + e.distance < dist[e.to]) {
          heap.add(new Info(e.to, info.distance + e.distance));
          dist[e.to] = info.distance + e.distance;
        }
      }

    }

  }

  static void findCity() {
    int num = 0;
    for (int i = 1; i <= N; i++) {
      if (dist[i] == K) {
        System.out.println(i);
        num++;
      }
    }
    if(num == 0 ){
      System.out.println(-1);
    }
  }

  public static void main(String[] args) {

    input();
    dijkstra();
    findCity();

  }
}