이번 문제는 BFS를 통해 해결하였다. 이 문제에서 중요한 점은 역과 역 간의 연결을 인접 리스트로 나타내면 시간과 메모리 제한에 걸린다는 것이다. 그래서 각 역을 나타내는 리스트 stations에는 각 역이랑 연결된 노선의 번호를 담아야 하고, 노선 정보를 담은 리스트 lines에는 현재 노선에 있는 역들의 번호를 담아야 한다. 즉, 둘 다 2차원 리스트로 만들어져야 한다.

그리고 BFS를 통해 탐색을 진행한다. 이때 각 역과 노선에 대한 방문 처리를 따로 따로 진행해주어야 한다. 역의 방문 처리 리스트에는 환승 횟수가 들어가고, 노선의 방문 처리 리스트는 해당 노선에 방문했는지 여부만 판별한다. 이와 같은 방법으로 이 문제를 해결하였다.

Code

from collections import deque
n, l = map(int, input().split())
stations = [[] for _ in range(n+1)]
lines = []
for i in range(l):
    tmp = list(map(int, input().split()))
    lines.append(tmp[:-1])
    for j in range(len(tmp)-1):
        stations[tmp[j]].append(i)
start, end = map(int, input().split())
def bfs():
    if start == end:
        return 0
    visited = [-1 for _ in range(n+1)]
    visited_line = [False for _ in range(l)]
    q = deque()
    for line in stations[start]:
        q.append((start, line))
        visited_line[line] = True
    visited[start] = 0
    if start == end:
        return 0
    while q:
        cur, cur_l = q.popleft()
        if cur == end:
            return visited[cur]-1
        for nxt in lines[cur_l]:
            if visited[nxt] == -1:
                visited[nxt] = visited[cur]+1
                for nxt_l in stations[nxt]:
                    if not visited_line[nxt_l]:
                        q.append((nxt, nxt_l))
    return -1
print(bfs())