문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: 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)
