백준 5214번: 환승 (JAVA)

문제

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

입력

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

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

출력

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

 

---

 

풀이

 

1. 그래프를 인접 행렬로 저장: 역이 최대 10만개, N^2 == 100억 -> 애초에 memory에서 불가능

2. 그래프를 인접 리스트로 저장: 인접 리스트로 옮기는 과정은 O(NK^2), 최대 10억번 연산 -> 시간 초과

3. 그러면 어떻게 해야할까? 잘 모르겠어서 검색을 해 보았다.

방법: 하이퍼루프 자체를 노드로 본다. 이게 뭔 소리일까? 아래 그림을 보면 이해가 바로 될 것이다.

백문이 불여일견, 문제 예시에 대한 그래프 표현. (출처: Above & Beyond 님 블로그 https://t-anb.tistory.com/17)

그리고, dfs든 bfs든 그래프 탐색 시 하이퍼루프 노드로 갈 때에는 이동거리를 늘리지 않고, 실제 노드로 갈 때에만 이동거리를 늘리는 방식으로 구현하면 된다.

※ 가장 먼저 도달한 경로가 최단 경로임이 보장되는가?

• 그림을 보면 알 수 있듯이, 실제 노드는 서로 전혀 연결되어 있지 않으며, 하이퍼루프 노드와 실제 노드끼리만 연결이 있다. 따라서 1에서 N을 간다고 하면, 어떠한 경로이든 하이퍼루프 노드, 실제 노드를 번갈아가면서 가기 때문에 가장 먼저 도착한 경로는 최단 경로가 된다.
• 위 관찰을 이용하여, 그냥 distance[1] = 1로 설정하고, 어떤 노드에 도착하든 거리를 1씩 늘린 후 특정 점 N까지의 거리 = distance[N]/2 + 1로 계산해도 된다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		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.offer(1);
		visited[1] = true;
		distance[1] = 1;
		while (!queue.isEmpty()) {
			int from = queue.poll();
			for (int to: graph.get(from)) {
				if (visited[to]) continue;
				visited[to] = true;
				distance[to] = distance[from]+1;
				queue.offer(to);
			}
		}

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

}