클라우드로 크고 싶은 블로그 입니다

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

 

파이썬으로 아래와 같이 구현하였다.

 

import sys
from collections import deque

input = sys.stdin.readline

n, l = map(int, input().split())
station_visited = [0] * (n + 1) # 각 역의 깊이 저장 (환승 횟수)
line_visited = [0] * (l + 1) # 해당 노선을 이용한 적 있나?
subway = [list(map(int, input().split())) for _ in range(l)]
graph = [[] for _ in range(n + 1)]

for i in range(l):
    for j in subway[i]:
        if j == -1:
            break
        graph[j].append(i)

start, end = map(int, input().split())

q = deque()

# 큐에 시작 역 추가 후 방문 처리
q.append(start)
station_visited[start] = 1
flag = 0
while q:
    cur = q.popleft()

    # 목적지 까지 도착했다면
    if cur == end:
        if start == end:
            # 시작과 끝이 같은 경우 환승 없음
            print(0)
        else:
            print(station_visited[cur] - 2)
        flag = 1
        break

    for i in graph[cur]:
        # 해당 역에 도착하는 노선들
        if line_visited[i]:
            # 노선 중 이미 방문한 노선이 있다면 패스
            continue

        # 노선을 방문 처리
        line_visited[i] = 1

        for j in subway[i]:
            # 해당 노선이 운행하는 역들 목록을 가져와
            if station_visited[j] or j == -1:
                # 이미 방문한 적이 있으면 패스
                continue

            # 역 방문한 적이 없다면 현재 방문한 라인 에서 1단계 깊은 곳이므로 추가
            # 단 시작점은 0 단계, 시작점과 같은 라인은 1단계...따라서 최종 결과에서 -2 함
            # 시작점이 환승 역인 경우, 이미 방문한 노선은 line_visited 에서 처리 되므로 중복 처리 안됨
            station_visited[j] = station_visited[cur] + 1
            q.append(j)

if not flag:
    # 목적지에 도달할 수 없다면 -1 출력
    print(-1)