[파이썬] 백준 5214번: 환승 (BFS)

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

5214번: 환승

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

예제 입력 1 복사

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

예제 출력 1 복사

4

1-3-6-9나 1-5-6-9로 이동하면 된다.

 

## BFS, 핵심 아이디어: 하이퍼튜브도 같이 노드로 포함하여 접근
import sys
from collections import deque
input=sys.stdin.readline

# 역의 개수(n), 간선의 개수(k), 하이퍼튜브의 개수(m)
n,k,m=map(int,input().split())
# 그래프(n개의 역과 m개의 하이퍼튜브는 모두 노드임)
graph=[[] for _ in range(n+m+1)]
for i in range(1,m+1):
    arr=list(map(int,input().split())) # 하나의 하이퍼튜브 안에 포함된 역들 입력받음
    for x in arr:
        # 하이퍼튜브의 노드 번호는 n+1번부터 시작
        graph[x].append(n+i) # 노드 -> 하이퍼튜브
        graph[n+i].append(x) # 하이퍼튜브 -> 노드
        
visited=[False]*(n+m+1)
visited[1]=True # 1번 노드에서 출발
q=deque()
q.append((0,1)) # 거리, 노드 번호
found=False
while q:
    cost,now=q.popleft()
    if now==n: # n번 노드에 도착한 경우
        print(cost//2+1) # 절반은 하이퍼튜브 거리이므로 빼기
        found=True
        break
    for nx in graph[now]: # 인접한 노드 확인
        if visited[nx]==False: # 아직 방문하지 않았다면
            q.append((cost+1,nx))
            visited[nx]=True # 방문처리
            
# n번 노드에 도달이 불가능한 경우
if not found:
    print(-1)