[백준 2021번] 최소환승경로(파이썬)

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

2021번: 최소 환승 경로

이 문제에서 구현해야할 부분은

'어떻게 경로가 만나는 걸 표현할지'입니다.

처음에 저같은 경우에는

경로의 숫자 하나하나를 탐색하면서

다른 루트에 있는지 확인하는 쪽으로 갔습니다.

근데 이 방식은 경로가 많아질수록

시간초과가 어마어마하게 된다는 단점이 있습니다.

그래서 미리미리미리

'어떤 역은 몇번 경로랑 겹친다'

라는 걸 구현해주면서 문제를 풀었습니다.

#백준 2021번 최소환승
from collections import deque
N,L=map(int,input().split())
road=[]
tre=[[]for _ in range(N+1)]
for i in range(L):
    tmp=list(map(int,input().split()))
    for k in tmp:
        if k==-1:
            continue

        tre[k].append(i)
    road.append(tmp)

S,E=map(int,input().split())

visited=[1e9]*L


q=deque()
#처음에 S가 어디있는지 구해보자
for i in range(L):
    if S in road[i]:
        q.append([i,0])
        visited[i]=0

answer=1e9
while q:
    way,cnt=q.popleft()
    if cnt>visited[way]:
        continue
    if E in road[way]:
        answer=min(answer,cnt)
        continue

    for i in range(len(road[way])):
        go=road[way][i]
        if go==-1:
            continue
        on=tre[go]

        for co in on:

            if co==way:
                continue
            if visited[co]>visited[way]+1:
                visited[co]=visited[way]+1
                q.append([co,cnt+1])

if answer==1e9:
    answer=-1
print(answer)

그래프 탐색에서 많이 보이는 문제로

다익스트라로 분류할 수 있는 문제입니다.

문제를 풀어보시면서

다익스트라 관련 유형도 접해보시면 좋을 겁니다.

제가 놓칠뻔한 부분은 2가지인데요

 

1. cnt가 현재 경로의 환승보다 클 경우에는

스킵해주는 것.

 

2. 경로의 숫자가 현재경로+1보다 클 때만 넘어가주기

 

처음에는 이 2가지를 놓쳐서

시간초과가 떴다가

이후에 이 부분을 수정해주니 통과되었습니다.

저 부분을 놓치면

계속 계산이 돌아가게 되면서

프로그램이 계속 작동할 수 있으니

주의해주시면 좋습니다.