[python] 백준 5214 환승

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

5214번: 환승

 

문제 해결

• BFS를 이용하면 쉽게 풀릴 것 같은 느낌이 든다.
• 문제는 하이퍼튜브로 두개의 역만 묶는 것이 아나리 두 개 이상의 역이 묶일 수 있다는 것이다.
• 그리고 메모리를 신경써야한다.
• BFS를 돌 때 역마다 방문했는지 체크하는 것이 아니라 어떤 하이퍼튜브를 이용했는가도 고려대상이 된다.

 

문제 해결

from collections import deque

def bfs():
    visited_station = [0]*(n+1)
    visited_hyper = [0]*m
    que = deque()
    que.append((1,1))
    visited_station[1] = True
    while que:
        now, cnt = que.popleft()
        next_hyper = []
        for hyper_idx in stations[now]:
            if not visited_hyper[hyper_idx]:
                next_hyper.append(hyper_idx)
                visited_hyper[hyper_idx] = 1
        for hyper in next_hyper:
            for station in hyper_tube[hyper]:
                if not visited_station[station]:
                    if station == n:
                        return cnt + 1
                    visited_station[station] = 1
                    que.append((station,cnt+1))
    return - 1
if __name__=='__main__':
    n, k, m = map(int, input().split())
    stations = [[] for _ in range(n+1)]
    hyper_tube = [[] for _ in range(m)]
    for i in range(m):
        X = list(map(int, input().split()))
        for num in X:
            stations[num].append(i)
            hyper_tube[i].append(num)
    if n==1:
        print(1)
    else:
        answer = bfs()
        print(answer)