[Python/BOJ] 16166. 서울의 지하철

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

16166번: 서울의 지하철

문제

한국에 처음 도착한 미국인 Mr.Goofcode는 한국의 수도 서울을 여행할 생각에 들떠 있었다. 하지만, 공항 철도를 타고 서울역에 도착한 Mr.Goofcode는 복잡한 서울의 지하철 노선도를 보고 경악을 금치 못했다. 왜냐하면, 서울역을 포함한 서울의 모든 역은 이름이 아닌 숫자로 구분해야 했으며, 운영되는 지하철의 종류(호선)가 너무 많아 최적의 이동 경로를 계산하기 어려웠기 때문이다.

Mr.Goofcode는 패닉에 빠져 평소 메일로 편지를 주고 받던 당신에게 도움을 요청했다. 평소 Mr.Goofcode에게 도움을 받았던 당신은 그를 위해 지하철 노선도 어플리케이션을 만들어 주려고 한다. 그러나, 까다로운 Mr.Goofcode는 걷는 것을 매우 싫어한다. 따라서, 그를 위해 가능하면 어플리케이션이 제시하는 지하철 환승 횟수를 최소로 줄이고 싶어 한다.

Mr.Goofcode를 위해 주어진 지하철 노선도를 보고 Mr.Goofcode가 목적지에 도달하기 위해 최소 몇 번의 환승이 필요한지 구해주자. 단, Mr.Goofcode의 출발역인 서울역의 역 번호는 항상 0번이다.

지하철의 '호선'이란 한 종류의 지하철에서, 다른 지하철로 환승하지 않고 이동할 수 있는 역의 집합을 의미한다. 지하철의 '역'이란 지하철의 호선의 원소로 지하철이 방문할 수 있는 정점을 의미한다. 각 역은 간선으로 연결 관계를 나타낼 수 있으며, 이 간선을 통해서만 지하철이 이동할 수 있다. 지하철은 양 방향으로 이동할 수 있다.

입력

첫째 줄에 서울의 지하철 호선의 개수 N(1 ≤ N ≤ 10)이 주어진다.

둘째 줄부터, 순서대로 1호선부터 N호선까지, 각 호선의 역 개수 K(1 ≤ K ≤ 10)와 각 지하철 호선이 포함하는 역의 번호aN1, aN2, aN3, ... aNK가 한 줄에 주어진다. 각 역의 번호는 모두 다르며 0이상 232-1 이하의 정수임이 보장되어 있다.

입력의 마지막 줄에는, 도착역의 번호가 주어진다.

각 지하철 호선 중, 순환선이 있을 수 있음에 주의하자, 순환선의 입력은 호선이 포함하는 역의 번호가 a1, a2, a3, ... aK-1, a1 의 꼴로 주어진다. (예제 2번)

출력

출발 역(서울 역)에서 도착 역까지 최소 환승 횟수를 한 줄에 출력한다. 단, 도달할 수 없는 경우 -1을 출력한다.

풀이

Code

import sys, math
input = sys.stdin.readline

# 1. dfs 함수 정의
def dfs(sub, station, count) :
    global min_count
    # 1-1. 종료 조건 설정
    # 도착지가 노선 내에 있는 경우
    if destination in subway[sub] :
        min_count = min(min_count, count)
        return
    # 최솟값을 넘긴 경우
    if count >= min_count : return

    # 1-2.
    for next in subway[sub] :
        for i in range(1, n+1) :
            # 방문하지 않은 지하철 호선 중 현재 지하철 노선의 정차역이 있는 경우
            if i != station and next in subway[i] and not visited[i]:
                visited[i] = True
                # dfs 함수 실행
                dfs(i, next, count+1)
                visited[i] = False

n = int(input())
subway = [0] * (n+1)
# 2. 출발역이 노선에 포함된 지하철 호선 리스트 생성
starting_point = []
min_count = math.inf

# 3.
for i in range(1, n+1) :
    subway_num = list(map(int, input().split()))[1:]
    # 3-1. 출발지가 지하철 노선에 포함되는 지하철역 append
    if 0 in subway_num : starting_point.append(i)
    # 3-2. 각 호선별 노선 정보 입력 (중복 역 제거)
    subway[i] = list(set(subway_num))

destination = int(input())

# 4. 출발역에서 지하철 탑승
for i in starting_point :
    visited = [False] * (n+1)
    dfs(i, 0, 0)

# 5. 결과 출력
print(min_count) if min_count != math.inf else print(-1)