[Python] boj no. 2021 : 최소 환승 경로

Problem

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

Idea

주어진 노선 정보를 통해 그래프를 만들어 너비 우선 탐색을 이용하여 풀이했다.

이 때, 간선에 몇 번째 노선인가에 대한 정보를 추가로 저장하여 탐색 과정에서 다른 노선을 사용하는 환승 과정이 발생할 경우 이를 카운트하도록 하였다.

0-1 bfs를 응용하여 같은 노선을 이용하는 경우 환승 횟수가 동일하므로 덱의 전단에, 환승이 발생하는 경우 덱의 후단에 삽입하므로서 처음으로 목적지로 도착할 때의 환승 횟수가 최소 횟수임을 보장할 수 있도록 했다.

Code

import sys
from collections import deque

def bfs(start, end):
    dq = deque()
    visited = [False for _ in range(N+1)]
    visited[start] = True
    
    for lane, station in edge[start]:
        dq.append((0, lane, station))
        
    while dq:
        trans, lane, station = dq.popleft()
        if station == end:
            return trans
        
        if visited[station] == False:
            visited[station] = True
        
            for l, s in edge[station]:
                if lane == l:
                    dq.appendleft((trans, lane, s))
                else:
                    dq.append((trans+1, l, s))
    
    return -1

input = sys.stdin.readline

N, L = map(int, input().split())
edge = [[] for _ in range(N+1)]
for i in range(L):
    lane = list(map(int, input().split()))
    for j in range(1, len(lane)-1):
        edge[lane[j-1]].append((i, lane[j]))
        edge[lane[j]].append((i, lane[j-1]))

start, end = map(int, input().split())
if start == end:
    print(0)
else:
    print(bfs(start, end))

Comment