[BOJ 5214] 환승

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

5214번: 환승

 

역과 역 사이에 간선을 만들면 시간초과다.

왜냐하면 하이퍼큐브는 M개이고 하이퍼큐브가 연결하는 역의 갯수가 K인데

K(K-1)개의 간선을 M개에 대해서 다 만들면 1억이 넘기 때문에..

 

 

풀이 1)

 

따라서 하이퍼튜브를 하나의 노드로 만들자.

이 때 [역 -> 하이퍼튜브]는 간선이 0이고 [하이퍼튜브 -> 역] 또는 [역 -> 역]은 간선이 1이다.

(여기서 [역 -> 역] 간선은 만들지 않았다.)

 

그래프 모델을 위와 같이 만들면 노드는 (N + M)개고 간선은 (K * M * 2)개다.

(노드는 최대 101,000개, 간선은 최대 2,000,000개)

 

이렇게 그래프를 만들고 나면 굉장히 편하다!

정점, 간선의 수와 가중치가 서로 다른 것을 보고 최단 경로 알고리즘(다익스트라)를 바로 적용하면 되기 때문이다.

하지만 가중치가 0 또는 1이면 적용할 수 있는 0-1 BFS라는 더 쉬운 최단 경로 알고리즘이 있다.

 

0-1 BFS는 간단하다. BFS에서 queue를 deque로 바꾸고 push할 때만 아래와 같이 신경써주자.

1. 가중치가 0이면 deque의 앞에 push한다.
2. 가중치가 1이면 deque의 뒤에 push한다.

0-1 BFS의 정당성은 다익스트라와 같다.

 

from collections import deque
N, K, M = map(int, input().split())

# 0 ~ N - 1     : 역
# N ~ N + M - 1 : 하이퍼튜브
adj = [[] for _ in range(N)] + [list(map(int, input().split())) for _ in range(M)]

# (역 -> 하이퍼튜브) 연결
for i in range(M):
    for k in adj[N + i]:
        adj[k - 1].append(N + i + 1)

# 0-1 bfs 
q = deque([1])
vst = [0] * (N + M)
vst[0] = 1

while q:
    u = q.popleft()
    for v in adj[u - 1]:
        if vst[v - 1]: continue
        if v > N:
            vst[v - 1] = vst[u - 1]         # 하이퍼튜브 -> 역
            q.appendleft(v)                 # vst에 0을 더하고 push_left
        else:
            vst[v - 1] = vst[u - 1] + 1     # 나머지 경우
            q.append(v)                     # vst에 1을 더하고 push_right

# 만약 vst == 0 이면 -1 출력
if vst[N - 1]:
    print(vst[N - 1])
else:
    print(-1)

 

 

 

풀이 2)

 

어차피 [역 -> 역], [하이퍼튜브 -> 하이퍼튜브] 간선은 없다.

 

따라서 이동 경로는 [역 -> 하이퍼튜브 -> 역 -> 하이퍼튜브.. ] 이렇게 번갈아서 나타난다.

 

그렇다는건

 

1. 무조건 역에서 역에 도달하면 (이동한 횟수/2)를 하면 답이 나온다.

 

2. 원래는 최단 경로를 구하기 위해서는 현재 노드가 역일 때 가중치가 0인 하이퍼튜브로 먼저 이동해야한다.

하지만 역에서 역으로 가는 간선은 없기 때문에 역에서는 무조건 하이퍼튜브로 이동한다.

 

위 정당성을 가지고 풀이 1에서 모든 간선의 가중치를 1로 바꾸고

 

BFS를 적용해서 답을 2로 나눠도 AC를 받는다.