[백준/5214] 환승 (Python)

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

5214번: 환승

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:39:35

 

---

 

문제 설명

 

 

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

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

 

출력 예시

 

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

  

 

---

 

풀이

 

단순한 그래프 탐색으로 문제를 풀기에는, 하이퍼튜브의 크기 K 가 3 이상일 수 있다. 하이퍼튜브의 크기가 K일때 내부 노드들의 총 엣지 수는 K*(K-1) // 2 가 된다. 기본적으로 탐색 알고리즘은 엣지 수 E와 노드 수 V와 깊이 연관되어 있다. 이를테면 BFS의 경우 시간복잡도는 O(E+V)가 되며, E 는 M * K^2에 비례한다. M, K 모두 10^3까지 가능하므로 이는 필연적으로 시간 초과를 일으킨다.

 

즉 우리는 K^2인 하이퍼튜브의 엣지 변환 과정을 개선할 필요가 있다. 그 중 하나의 방법은, 하이퍼튜브 자체를 하나의 노드로 인식하는 것이다. 하이퍼튜브에 포함된 각 역들은 들어갈 때 혹은 나갈 때 과정에서 총 1의 시간이 소요된다(들어갈 때에 1이 소요된다면 나갈 때에 0이 소요되는 방식이다) 즉 이 때 노드 수는 O(N + M)개로 변화하며, 한 하이퍼튜브당 엣지 개수는 K개이다. 같은 BFS로 문제를 풀이한다면 O(E+V) = O(N+M+K)가 되므로 제한시간 내 풀이 가능하다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
MAX = float('inf')
N, K, M = map(int, input().split())

adj_nodes = [list() for _ in range(M+N)]

for i in range(N, N+M) :
  line = list(map(int, input().split()))
  for j in line :
    adj_nodes[j-1].append((i, 1))
    adj_nodes[i].append((j-1, 0))

visited = [MAX]*(N+M)
visited[0] = 0
q = deque([(0, 1)])

while q :
  node, dist = q.popleft()
  if node == N-1 :
    print(dist)
    exit()
  for adj, cost in adj_nodes[node] :
    if visited[adj] > dist + cost :
      visited[adj] = dist + cost
      q.append((adj, dist+cost))
print(-1)

풀이 완료!