이번 문제는 BFS를 통해 해결하였다. 처음에는 주어진 모든 입력에 대하여 간선을 인접 리스트로 생성하였다. 그러나 이 방식으로 데이터를 관리할 경우 메모리 초과가 발생하였다. 그래서 질문하기를 참고하였고, 간선을 일일히 생성하지 않고, 역 리스트에는 연결된 튜브 번호를, 튜브 번호에는 연결된 역들을 저장하는 방식으로 접근하였다.

BFS로 1번 역부터 탐색을 시작하여 1번 역과 연결된 튜브 중 방문하지 않은 튜브만을 따로 리스트에 담고, 다음 튜브 리스트를 순회하며 그 튜브와 연결된 역들에 방문하도록 하였다. 이 과정에서 n번 역에 도착할 경우 그때의 cnt변수를 반환하였고, while문이 끝날 때까지 반환값이 없다면 -1을 반환하였다.

Code

from collections import deque
n, k, m = map(int, input().split())
station = [[] for _ in range(n+1)]
tube = [[] for _ in range(m)]
for i in range(m):
    nums = list(map(int, input().split()))
    for num in nums:
        station[num].append(i)
        tube[i].append(num)
def find_way():
    q = deque()
    q.append((1, 1))
    visited_station = [False for _ in range(n+1)]
    visited_tube = [False for _ in range(m)]
    visited_station[1] = True
    while q:
        cur, cnt = q.popleft()
        if cur == n:
            return cnt
        nxt_tube = []
        for nxt in station[cur]:
            if not visited_tube[nxt]:
                nxt_tube.append(nxt)
                visited_tube[nxt] = True
        for nxt in nxt_tube:
            for idx in tube[nxt]:
                if not visited_station[idx]:
                    visited_station[idx] = True
                    q.append((idx, cnt+1))
    return -1
print(find_way())