[백준] 2021 최소 환승 경로 python

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

2021번: 최소 환승 경로

import sys; input = sys.stdin.readline
from collections import deque
N, L = map(int, input().split())
station = [list() for _ in range(N+1)]
line = [list() for _ in range(L)]
for i in range(L):
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        if tmp[j] == -1: break
        station[tmp[j]].append(i)    # 역에 연결되어있는 라인
        line[i].append(tmp[j])  # 라인에 연결되어있는 역

START, END = map(int, input().split())
def bfs(START, END):
    if START == END: return 0
    visit = [-1 for _ in range(N + 1)]
    visit_line = [False for _ in range(L)]
    q = deque()
    visit[START] = 0
    for tmp_line in station[START]:
        q.append((START, tmp_line))
        visit_line[tmp_line] = True
    while q:
        cur_node, cur_line = q.popleft()
        # print(cur_node, cur_line)
        for adj_node in line[cur_line]:
            if visit[adj_node] != -1: continue
            if adj_node == END:
                return visit[cur_node]
            visit[adj_node] = visit[cur_node] + 1
            for connected_line in station[adj_node]:
                if visit_line[connected_line]: continue
                q.append((adj_node, connected_line))
    return -1

print(bfs(START,END))

난이도가 꽤 높은 BFS 문제이다. 어떻게 풀어야할지 찾아가는게 조금 어려웠다. 

처음엔 교차역을 찾아서 bfs로 돌렸으나 교차역을 찾는것이 너무 오래 걸려서 시간초과가 났다. 

그래서 모든 역마다 bfs를 돌리는 것으로 바꾸어서 성공하였다. 

 

 

11 6
1 2 3 4 -1
4 5 6 -1
6 7 8 -1
8 9 10 -1
10 11 -1
1 11 -1
1 10

24 6
1 2 3 4 -1
4 5 6 -1
6 7 8 -1
8 9 1 -1
6 10 11 -1
8 12 13 11 -1
1 1