5214번 : 환승

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

5214번: 환승

 

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

 

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

 

---

소스코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 역 개수
        int K = Integer.parseInt(st.nextToken()); // 하이퍼 듀브 연결 개수
        int M = Integer.parseInt(st.nextToken()); // 하이퍼 튜브 개수

        // 하이퍼루프도 노드로 보자: x번째 하이퍼루프를 N+x index에 할당
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= N+M; i++) {
            graph.add(new ArrayList<Integer>());
        }
        boolean[] visited = new boolean[N+1+M];
        int[] distance = new int[N+1+M];

        // 인접 리스트 구현
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < K; j++) {
                int temp = Integer.parseInt(st.nextToken());
                graph.get(temp).add(N+i+1); // 하이퍼 튜브 연결
                graph.get(N+i+1).add(temp); // 하이퍼 튜브에 정점 연결
            }
        }

        // BFS
        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.add(1);
        visited[1] = true;
        distance[1] = 1;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int nx: graph.get(now)) {
                if (visited[nx]) continue;
                visited[nx] = true;
                distance[nx] = distance[now] + 1;
                queue.offer(nx);
            }
        }

        System.out.println(visited[N]? distance[N]/2 + 1: -1);
    }
}

 

해결방법

1. 그래프를 인접 행렬로 저장하는 경우, 역이 최대 10만 개이고 N^2 (100억) 크기의 메모리를 필요로 하므로 메모리 초과 문제가 발생한다.

2. 그래프를 인접 리스트로 저장하는 경우, 그래프를 인접 리스트로 옮기는 과정에서 O(MK^2) 시간이 소요되며, 최대 10억 번의 연산이 필요하므로 시간 초과 문제가 발생한다.

 

따라서 이 문제를 해결하기 위해서는 하이퍼 루프를 노드로 간주하고 다른 방식으로 접근해야 한다.

출처: Above & Beyond 님 블로그 https://t-anb.tistory.com/17

• 하이퍼 루프 자체를 노드로 본다면 그래프를 인접 리스트로 저장하는데 시간 복잡도는 O(MK)가 되므로 적합하다
• 그림을 통해 확인할 수 있듯이, 실제 노드는 서로 전혀 연결되어 있지 않으며, 하이퍼루프 노드와 실제 노드끼리만 연결이 되어있다. 따라서 1에서 N을 간다고 하면, 어떠한 경로이든 하이퍼루프 노드, 실제 노드를 번갈아가면서 가기 때문에 가장 먼저 도착한 경로가 최단 경로가 된다.
• 위 관찰을 이용하여, 초기에 distance[1] = 1로 설정하고, 어떤 노드에 도착하든 거리를 1씩 늘린 후 특정 점 N까지의 거리 = distance[N]/2 + 1로 계산하면 최단 거리를 구할 수 있다.