[BOJ/백준] 5214 환승 파이썬

문제 링크 : https://www.acmicpc.net/problem/5214

5214번: 환승

 

역이랑 하이퍼튜브를 어떻게 표현할까를 고민했던 문제이다.

나는 각 역에 연결된 하이퍼튜브의 번호 배열, 각 하이퍼튜브가 연결한 역의 번호

두가지를 사용했으며 각각은 인접리스트로 했다.

입력 순서대로 하이퍼 튜브에 0번부터 번호를 매겨서 저장했다.

 

설명하면 아래와 같다.

하이퍼 튜브가

1 2 3

1 4 5

라고 들어 왔다고 해보자.

 

각 역에 연결된 하이퍼튜브의 번호 배열 배열은

[(0,1),0,0,1,1] 이 될것이다.

즉 0번 역은 0,1 하이퍼튜브가 연결됐다는 것이다.

 

 

각 하이퍼튜브가 연결한 역의 번호

0번 하이퍼튜브에 1 2 3

1번 하이퍼튜브에 1 4 5가 있다.

 

이것을 가지고 BFS를 돌렸다.

일단 BFS는 현재 역의 번호를 저장한다.

 

그리고 두번의 과정을 거쳐 다음 역을 확인한다.

 

1. 현재 역에 연결된 하이퍼튜브 확인

 - 방문하지 않았고 현재 역과 연결된 하이퍼튜브의 번호를 구한다.

 

2. 구한 하이퍼튜브를 확인해 다음역 큐에 넣기

 - 하이퍼튜브에 연결된 역 중 아직 방문하지 않은 역을 방문한다.

 - 이때 마지막 역인지 검사 후 맞다면 종료한다.

 

한가지 주의할점이라면 역이 1개인 경우는 따로 체크해주자.

나는 정답 확인을 위의 2번 과정에서 확인을 하기 때문에 역이 1개인 경우는 해당과정으로 들어오지 않는다.

 

from sys import stdin
from collections import deque

input = stdin.readline

n,k,m = map(int, input().split())
station = [[] for _ in range(n)]
hyper_tube = [[] for _ in range(m)]
for idx in range(m):
    nums = list(map(int, input().split()))
    for num in nums:
        station[num-1].append(idx)
        hyper_tube[idx].append(num-1)

def solv():
    visited_station = [False]*n
    visited_hyper = [False]*m
    q = deque([(0,1)])

    visited_station[0] = True
    while q:
        now,cnt = q.pop()

        nxt_hyper = []
        for hyper_idx in station[now]:
            if not visited_hyper[hyper_idx]:
                nxt_hyper.append(hyper_idx)
                visited_hyper[hyper_idx] = True

        for hyper in nxt_hyper:
            for station_idx in hyper_tube[hyper]:
                if not visited_station[station_idx]:
                    if station_idx == n-1:
                        print(cnt+1)
                        return
                    visited_station[station_idx] = True
                    q.appendleft((station_idx,cnt+1))
    print(-1)

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