[백준] [파이썬] [Graph] 5214번: 환승

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

5214번: 환승 문제 보러 가기

제한시간: 2초
메모리 제한: 256 MB

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 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] 하이퍼에서 (1)역에서 (3)역까지 

[3] 하이퍼에서 (3)역에서 (6)역까지 

[5] 하이퍼에서 (6)역에서 (9)역까지 가면 된다. 이러면 1-3-6-9 로 4번만에 

또는 

[2] 하이퍼에서 (1)역에서 (5)역까지 

[4] 하이퍼에서 (5)역에서 (6)역까지 

[5] 하이퍼에서 (6)역부터 (9)역까지 가면 된다. 이러면 1-5-6-9로 4번만에 간다. 

 

dummy station으로 풀라고 하는데 그 풀이를 해석해보자. 

하이퍼와 역을 따로 만들지 말고 하나의 그래프에 정보를 넣는다. 

graph =[[] for _ in range(1+N+M)]

graph의 N+1번째 즉 10부터 하이퍼의 정보를 넣는다. 즉, [1] 하이퍼 [1,2,3]은 graph[10]=[1,2,3] 이고 

[2] 하이퍼 [1,4,5]는 graph[11]=[1,4,5]이다. 

 

graph의 1번째부터 9번째까지 역 1에 대한 하이퍼 정보를 연결한다. 즉 graph[1]에는 1역을 통과하는 하이퍼 index를 넣는다. graph[1]=[10,11]이 된다. 

 

다시 정리하면 

1. 경로의 노드를 "역"과 "하이퍼튜브"로 설정한다. 따라서 배열의 사이즈는 N+M+1이다

2. '역-하이퍼-역' 구조로 경로를 저장한다. 경로 배열의 1부터 N까지는 역, N+1부터 N+M까지는 하이퍼튜브

3. BFS로 길을 찾으면서 하이퍼튜브로 가면 이동 횟수에 변화를 주지 않고 역에 도착하면 횟수를 증가시킨다

4. 목적지에 도착하면 이동 횟수 출력

 

즉 하이퍼 노드로 가서 하이퍼 노드의 역 정보를 살피는데 역을 이동할때는 cnt+1이 되고 

하이퍼 노드에서 하이퍼 노드로 이동할 때는 역을 이동하는게 아니라서 cnt+1을 하지 않음 

 

cnt=1

[1] 하이퍼에서 (1)역에서 (3)역까지  --> 1역 노드에서 3역 노드로 cnt+=1을 한다

[3] 하이퍼에서 (3)역에서 (6)역까지 --> [1] 하이퍼에서 [3] 하이퍼로 이동하는데 cnt를 증가시킬 필요없다. 3노드에서 6노드로 이동 했으니 cnt+=1을 한다 

[5] 하이퍼에서 (6)역에서 (9)역까지 --> [3] 하이퍼에서 [5] 하이퍼로 이동하는데 cnt를 증가시킬 필요없다. 6노드에서 9노드로 이동했으니 cnt+=1을 한다 

이러면 1-3-6-9 로 4번만에 1에서 9로 도착한다.

---

BFS로 푼 정답 코드

import sys 
from collections import deque

sys.stdin=open('input.txt','r')

input=sys.stdin.readline

if __name__=="__main__":
    N,K,M=map(int, input().split())     # 9,3,5
    graph=[[] for _ in range(N+M+1)]    # # 1부터 N까지는 역, N이후부터는 hyper 정보 / dummy station을 만들어서 해결 
    for i in range(1,M+1):
        hyper=list(map(int, input().split()))
        graph[N+i]=hyper            # 1부터 N까지는 역, N이후부터는 hyper 정보 
        for s in hyper:             # 하이퍼로 연결된 역
            graph[s].append(N+i)
    
    visited=[0]*(N+M+1)
    Q=deque()
    Q.append([1,1])             # 1은 현재 역, 1은 현재 역까지 오는데 걸린 거리
    visited[1]=1                # 시작은 1역 방문 

    while Q:
        sta,cnt=Q.popleft()     # 현재 역, 현재 역까지 오는데 걸린 거리
        if sta==N:              # 현재 역이 목표 역인 N에 도착 하면 
            print(cnt)          # 지금까지 오는데 걸린 거리 출력하고 
            sys.exit()          # 멈춤 
        for n in graph[sta]:    # 현재 역을 포함한 하이퍼, 현재 역을 통과하는 하이퍼의 역을 살펴봄 
            if visited[n]==0:   # 현재 역을 통과하는 하이퍼의 역을 살펴봄 
                visited[n]=1    # 첫 방문이면 방문 체크 
                if n>N:         # 하이퍼인 노드를 살펴보고 있는 중이라면 N보다 큰 idx의 노드는 하이퍼 정보
                    Q.append([n,cnt])   # 하이퍼간의 이동은 cnt를 증가시킬 필요없다.
                else:           # 현재 역에 대한 노드를 살펴보는 중이라면 
                    Q.append([n,cnt+1]) # 현재 역, 현재 역으로 이동해서 거리+1
    print(-1)

 

---