[백준] 5214번 - 환승

📩 출처

문제

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

입력

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

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

출력

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

👉 생각

• 이 문제는 모든 역의 관계를 담는 인접리스트, 인접 배열로 접근하면 메모리 초과가 발생한다.
• 따라서 station 배열을 만들고 각 인데스는 해당 역에서 갈 수 있는 하이퍼튜브를 담고, hyper_tube의 인덱스는 해당 하이퍼튜브에서 갈 수 있는 역 정보를 담아준다.
• 1번역에서 시작하면 station에는 1번 역에서 갈수 있고 아직 방문하지 않은 하이퍼튜브를 체크한다.
• 하이퍼 튜브를 통해 1번에서 이동할 수 있는 곳을 모두 이동하고 방문하지 않은 역이라면 q에 넣어주면서 너비우선 탐색을 진행한다
• N번역에 도착하면 출력한다.

from collections import deque
import sys

def bfs():
    q = deque([(0,1)])
    visited = [0] * n
    visited[0] = 1
    visited_hyper = [0] * m
    while q:
        station, cnt = q.popleft()

        check = []
        for i in stations[station]:
            if not visited_hyper[i]:
                check.append(i)
                visited_hyper[i] = 1

        for hyper in check:
            for i in hyper_tube[hyper]:
                if not visited[i]:
                    if i == n - 1:
                        return cnt + 1
                    visited[i] = 1
                    q.append((i, cnt+1))
    return -1

n, k, m = map(int, input().split())
stations = [[] for _ in range(n)]
hyper_tube = [[] for _ in range(m)]

for i in range(m):
    numbers = list(map(int, sys.stdin.readline().split()))
    for num in numbers:
        hyper_tube[i].append(num - 1)
        stations[num - 1].append(i)

if n == 1: print(1)
else: print(bfs())