[Baekjoon] 환승 / Python, 파이썬 / 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을 출력한다.

예제 입력 1

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

예제 출력 1

4

1-3-6-9나 1-5-6-9로 이동하면 된다.

예제 입력 2

15 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 13

예제 출력 2

3

문제 풀이

import sys
from collections import deque

input = sys.stdin.readline

N, K, M = map(int, input().split())
graph = [[] for _ in range(N + M + 1)]

for i in range(1, M + 1):
    data = list(map(int, input().split()))
    for x in data:
        graph[x].append(N + i)
        graph[N + i].append(x)

visited = set([1])
q = deque([(0, 1)])
found = False

while q:
    cost, now = q.popleft()
    if now == N:
        print(cost // 2 + 1)
        found = True
        break
    for y in graph[now]:
        if y not in visited:
            q.append((cost+1, y))
            visited.add(y)

if not found:
    print(-1)