BOJ#5214 환승

BOJ#5214 환승

* 문제

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

* 풀이

하이퍼튜브는 M개만큼 있고, 각각의 하이퍼튜브는 K개의 노드를 연결하고 있다.

-> 간선 정보가 여태까지 풀어본 문제와는 다르게 주어짐

-> 간선 정보를 어떤 자료구조에 어떻게 담을지 고민

-> 인접 행렬은 메모리 초과 (N <= 100,000)

-> 각 하이퍼튜브는 최대 1000개의 노드 정보를 담고 있으므로, 이것을 일일이 짝을 맞추어가며 간선 정보를 저장하기 쉽지 않다.

생각한 아이디어는 다음과 같다.

각 하이퍼튜브에 연결된 노드 정보는 아래와 같고

1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

각 하이퍼튜브에 속하는 노드에 임의의 더미 노드를 생성하여 연결시킨다.

10 ↔ 1, 10 ↔ 2, 10 ↔ 3
11 ↔ 1, 11 ↔ 4, 11 ↔ 5
12 ↔ 3, 12 ↔ 6, 12 ↔ 7
13 ↔ 5, 13 ↔ 6, 13 ↔ 7
14 ↔ 6, 14 ↔ 8, 14 ↔ 9

N개의 노드는 N+M개가 되고, 간선은 N*M개가 된다.

이렇게 변환한 그래프에서 최단 경로 길이를 구한다. 최단 경로 길이를 dist[N]이라고 했을 때, 더미노드를 제외한 길이는 (dist[N] + 1) / 2가 된다 

위의 예에서 1 -> 9로 가는 최단 경로는

1 -> 3 -> 6 -> 9에서 위 과정을 거쳐

1 -> 10 -> 3 -> 12 -> 6 -> 14 -> 9가 된다.

총 7개의 노드에서 3개의 더미 노드를 제거하면 구하고자 하는 최소 역의 개수를 구할 수 있다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%235214_Transfer/src/Main.java

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

/**
 * BOJ#5214 환승
 * https://www.acmicpc.net/problem/5214
 */

public class Main {

    static final int INF = 10000000;

    static int[] dist = new int[101005];
    static boolean[] discovered = new boolean[101005];

    static {

        Arrays.fill(dist, INF);
    }

    public static void main(String[] args) throws IOException {

        int N; // 역의 개수 <= 100,000
        int K; // 하이퍼튜브가 서로 연결하는 역의 개수 <= 1,000
        int M; // 하이퍼튜브의 개수
        ArrayList<ArrayList<Integer>> edge = new ArrayList<ArrayList<Integer>>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= N + M; i++) {

            edge.add(new ArrayList<Integer>());
        }

        for (int i = 1; i <= M; i++) {

            st = new StringTokenizer(br.readLine());

            int dummy = N + i;

            for (int j = 0; j < K; j++) {

                int node = Integer.parseInt(st.nextToken());

                edge.get(dummy).add(node);
                edge.get(node).add(dummy);
            }
        }

        Queue<Integer> queue = new LinkedList<Integer>();

        queue.add(1);
        discovered[1] = true;
        dist[1] = 1;

        while (!queue.isEmpty()) {

            int u = queue.poll();

            if (u == N) {

                break;
            }

            for (int x : edge.get(u)) {

                if (!discovered[x] && dist[x] > dist[u] + 1) {

                    queue.add(x);
                    discovered[x] = true;
                    dist[x] = dist[u] + 1;
                }
            }
        }

        System.out.println(dist[N] >= INF ? -1 : (dist[N] + 1) / 2);
    }
}