백준 5214 환승 (파이썬)

https://www.acmicpc.net/problem/5214

5214번: 환승

기본적인 bfs로 길찾기를 하면 메모리 초과가 발생한다

이를 해결하기 위한 방법을 생각해내는게 쉽지 않은 문제

 

1. 경로의 노드를 역과 하이퍼튜브로 설정한다. 따라서 배열의 사이즈는 n+m이다

2. '역-하이퍼튜브-역' 구조로 경로를 저장한다. 경로 배열의 0부터 n-1까지는 역, n부터 n+m-1까지는 하이퍼튜브

3. bfs로 길을 찾으면서 하이퍼튜브로 가면 이동 횟수에 변화를 주지 않고 역에 도착하면 횟수를 증가시킨다

4. 목적지에 도착하면 이동 횟수 출력

from collections import deque
import sys

input = sys.stdin.readline

def bfs():
    q.append(0)
    c[0] = 1
    while q:
        x = q.popleft()
        if x == n-1:
            print(c[x])
            return
        for nx in a[x]:
            if not c[nx]:
                if nx >= n:
                    c[nx] = c[x]
                    q.append(nx)
                else:
                    c[nx] = c[x] + 1
                    q.append(nx)
    print(-1)

n, k, m = map(int, input().split())
a = [[] for _ in range(n+m)]
c = [0 for _ in range(n+m)]
q = deque()

for i in range(m):
    row = list(map(int, input().split()))
    for j in range(k):
        a[row[j]-1].append(n+i)
        a[n+i].append(row[j]-1)

bfs()