[백준 2021번] 최소 환승 경로 (Python3)

import sys,collections
input = sys.stdin.readline

def BFS():
  dq = collections.deque([(i,0) for i in graph[start]])
  visitedN = [0]*(N+1); visitedL = [0]*L
  while dq:
    now,cnt = dq.popleft()
    if visitedL[now]:
      continue
    visitedL[now] = 1
    for s in subway[now]:
      if s==end:
        return cnt
      if visitedN[s]:
        continue
      visitedN[s] = 1
      for next in graph[s]:
        if not visitedL[next]:
          dq.append((next,cnt+1))
  return -1

N,L = map(int,input().split())
subway = [[*map(int,input().split())][:-1] for i in range(L)]
start,end = map(int,input().split())

graph = [[] for i in range(N+1)]
for i in range(L):
  for s in subway[i]:
    graph[s].append(i)

print(BFS())

간단한 BFS 응용문제.

 

풀이를 설명하면,

1. 모든 지하철 역에 대해서 해당 역을 지나는 지하철 노선을 그래프에 넣는다.

2. visited 배열을 2개 만들어 하나는 역에 대한 visited, 하나는 노선에 대한 visited로 둔다.

3. 각 노선에 대해서 BFS로 최소환승횟수를 찾는다.

 

2번에서 visited 배열을 2개 만들지 않았더니 메모리 초과가 발생할 수 있다.

 

 

오늘의 교훈) 여러가지 문제를 풀어보자