백준 5214 - 환승

문제 링크 : https://www.acmicpc.net/problem/5214

 

풀이 과정

역 하나하나마다 간선을 연결하는 것은 너무 비효율적이다. 한 하이퍼튜브 안에서 모든 역은 연결되어 있기 때문이다.

한 하이퍼튜브가 서로 연결하는 역의 개수 K의 최대 제한이 1000이므로, 각 하이퍼튜브마다 K(K-1) 개의 단방향 간선을 생성해야 하는 일이 발생한다. 한 하이퍼튜브 안에서 단번에 다른 하이퍼튜브로 갈 수 있는 방법이 필요하다.

 

 

바로 하이퍼튜브 정점을 따로 만드는 것이다. 

하이퍼튜브 정점을 따로 만들면, 한 하이퍼튜브 안에 있는 역 정점들은 하이퍼튜브 정점 한 개를 거쳐서 바로 연결되고, 다른 하이퍼튜브 안에 있는 역 정점 또한 하이퍼튜브 정점을 거쳐서 바로 연결될 수 있다.

 

이 아이디어가 있으면, 한 하이퍼튜브 안에 있는 정점들을 모두 연결할 필요 없이, 하이퍼튜브 정점에 접근하는 것만으로도 자유롭게 이동할 수 있다. 하이퍼튜브 정점을 만듦으로써 거쳐가는 정점의 개수가 (경로 상 역 정점 - 1) 개 더 늘어난다.

 

# 5214 : 환승
import sys
from collections import deque
input = sys.stdin.readline

n, k, m = map(int, input().rstrip().split())
graph = [[] for _ in range(n+m+1)] # 역 정점 + 하이퍼튜브 정점
for i in range(m):
    arr = list(map(int, input().rstrip().split()))
    for a in arr:
        graph[n+i+1].append(a) # 하이퍼튜브 정점에 연결해준다.
        graph[a].append(n+i+1)
    
vis = [0 for _ in range(n+m+1)]
done = 0
queue = deque()
queue.append(1)
vis[1] = 1
time = 0
while queue: # BFS
    size = len(queue)
    for _ in range(size):
        now = queue.popleft()
        if now == n: 
            done = 1
            break
        for next in graph[now]:
            if vis[next] == 0:
                vis[next] = 1
                queue.append(next)
    if done: break
    time += 1

if done: print(time // 2 + 1) # 정점 개수 / 2 + 1
else: print(-1)