[Baekjoon] 환승

문제

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

입력

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

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

출력

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

예제

Example 1:

Input: 
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9
Output: 
4

Example 2:

Input:
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
Output:
3

조건

시간 제한 : 2초

메모리 제한 : 256 MB

풀이과정

풀이 1

dummy station을 만들어서 해결하였다.

from collections import deque
import sys

n, k, m = map(int, input().split())

graph = [[] for _ in range(n+m+1)]

for i in range(1, m+1):
    sub = list(map(int, input().split()))
    graph[n+i] = sub
    for s in sub:
        graph[s].append(n+i)

q = deque()

nvisited = [False] * (n+m+1)

q.append((1, nvisited,1))

nvisited[1] = True

while q:
    subway, visited, level = q.popleft()
    if subway == n:
        print(level)
        sys.exit()

    for s in graph[subway]:
        if visited[s] == False:
            visited[s] = True
            if s > n:
                q.append((s, visited, level))
            else:
                q.append((s, visited, level+1))

print(-1)