[백준/python/5214]환승


문제링크 : 환승

삼성 sw역량테스트를 대비하기 위해 기출문제 풀기를 시작했다.
너무 어려웠다..그래서 고민하다가 다른 블로그를 참고하여 풀었다.
우선 bfs를 사용해야 한다는 것은 알았지만 hyper와 station 배열을 어떻게 구상해야 하는지 어려웠던 것 같다.

다른 블로그를 참고하여 푼 나의 코드는 이렇다

import sys
from collections import deque

input=sys.stdin.readline
n,k,m=map(int, input().split())
station=[[]for _ in range(n)]
hyper=[[]for _ in range(m)]
for h in range(m):
    stations=list(map(int, input().split()))
    for s in stations:
        station[s-1].append(h)
        hyper[h].append(s-1)
def bfs():
    visited_station=[False]*n
    visited_hyper=[False]*m
    q=deque([(0,1)])  #0은 현재역, 1은 현재 역 방문횟수
    visited_station[0]=True

    while q:
        sta, cnt=q.pop()
        next=[]
        for hyper_idx in station[sta]:
            if not visited_hyper[hyper_idx]:
                next.append(hyper_idx)
                visited_hyper[hyper_idx]=True
        for hypers in next:
            for stations in hyper[hypers]:
                if not visited_station[stations]:
                    if stations==n-1:
                        print(cnt+1)
                        return
                    visited_station[stations]=True
                    q.appendleft((stations,cnt+1))
    print(-1)

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

이 문제를 풀면서 deque를 만드는 부분 deque([(0,1)]) 여기와 deque에 append 해주는 부분 q.appendleft((stations, cnt+1)) 의 형태가 차이 난다는 것을 처음 알았다. 이부분을 계속 똑같이 해주는바람에 오류가 났다.

더 발전해야겠고만~

좋은 웹페이지 즐겨찾기