[BOJ] 16166번 : 서울의 지하철 Java 풀이

여러 가지 자료구조를 사용해야 하는 문제이다.

먼저 제한을 자세히 살펴보고 문제를 해석해 보자.
지하철 노선의 개수는 10개뿐이다. 그리고 이 노선에 속하는 역이 입력으로 들어온다. 이때 역의 값은 최대 2^32-1까지 가능하다. 반면 역의 개수는 최대 10*10이 될 수 있다.

각 역에 도착하기 위한 최소 비용을 배열로 나타내기 위해서는 역을 압축해야 한다는 것을 알 수 있다. 따라서 0 ~ 2^32-1의 범위에 속하는 역들을 0 ~ 100에 해당하는 값으로 치환하는 작업을 수행하자.

결국 구하고 싶은 것은 몇 번 지하철을 갈아타는지이다. 따라서 지하철을 기준으로 도달할 수 있는 역들에 전부 방문을 표시하고, 역에서 환승할 수 있다면 환승을 하면 된다. 이때 방문 값이 1 증가하게 되고 우리는 이 값의 최소비용을 구해야 하므로 다익스트라를 함께 사용하면 문제를 해결할 수 있다.

추가로 비용은 무조건 1이기 때문에 BFS로도 최소 비용을 구할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Main {

  private static final PriorityQueue<Node> pq = new PriorityQueue<>();
  private static final Map<Integer, Integer> mp = new HashMap<>();
  private static final ArrayList<ArrayList<Integer>> subway = new ArrayList<>();
  private static final ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
  private static final int[] visited = new int[110];
  private static int count = 0;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    for (int i = 0; i < N; i++) {
      subway.add(new ArrayList<>());
      String[] s = br.readLine().split(" ");
      for (int j = 1; j <= Integer.parseInt(s[0]); j++) {
        int node = Integer.parseInt(s[j]);
        subway.get(i).add(node);
        if (mp.containsKey(node)) {
          adj.get(mp.get(node)).add(i);
        } else {
          adj.add(new ArrayList<>());
          mp.put(node, count);
          adj.get(count++).add(i);
        }
      }
    }
    dijkstra();
    int end = mp.get(Integer.parseInt(br.readLine()));
    if (visited[end] == 1000000000) {
      System.out.println(-1);
    } else if (end == 0) {
      System.out.println(0);
    } else {
      System.out.println(visited[end] - 1);

    }
  }

  private static void dijkstra() {
    for (int i = 0; i < 110; i++) {
      visited[i] = 1000000000;
    }
    pq.add(new Node(mp.get(0), 0));
    visited[mp.get(0)] = 0;
    while (!pq.isEmpty()) {
      Node node = pq.poll();
      int curr = node.node;
      int dist = node.dist;
      if (visited[curr] < dist) {
        continue;
      }
      for (int i = 0; i < adj.get(curr).size(); i++) {
        int nextSubway = adj.get(curr).get(i);
        for (int j = 0; j < subway.get(nextSubway).size(); j++) {
          int nextNode = mp.get(subway.get(nextSubway).get(j));
          if (visited[nextNode] <= dist + 1) {
            continue;
          }
          visited[nextNode] = dist + 1;
          pq.add(new Node(nextNode, dist + 1));
        }
      }
    }
  }

  static class Node implements Comparable<Node> {

    private final int node;
    private final int dist;

    public Node(int node, int dist) {
      this.node = node;
      this.dist = dist;
    }

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

}