[백준/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)) 의 형태가 차이 난다는 것을 처음 알았다. 이부분을 계속 똑같이 해주는바람에 오류가 났다.
더 발전해야겠고만~
Author And Source
이 문제에 관하여([백준/python/5214]환승), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@i_am_developer/백준python5214환승저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)