백준 5214 [환승] 파이썬

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

'

# 백준 5214 환승
import sys
from collections import deque

input = sys.stdin.readline
ans = -1

# N: 역 개수, K: 한 하이퍼튜브가 연결하는 역 수, M: 하이퍼튜브 개수
N, K, M = map(int, input().split())

# 역 방문 여부 기록
visited = [False for _ in range(N + 1)]

# 일반적인 인접 리스트 그래프
graph = [[] for _ in range(N + 1)]

# M개의 하이퍼튜브 정보 입력
for _ in range(M):
    loop = list(map(int, input().split()))
    
    # K개의 역을 모두 연결 (완전 연결)
    for i in range(K):
        for j in range(i + 1, K):
            graph[loop[i]].append(loop[j])
            graph[loop[j]].append(loop[i])  # 양방향 연결

# BFS 탐색
q = deque()
visited[1] = True
q.append((1, 1))  # (현재 역, 방문 횟수)

while q:
    station, cnt = q.popleft()
    
    # 도착역이면 종료
    if station == N:
        ans = cnt
        break

    # 연결된 역들을 탐색
    for next_station in graph[station]:
        if not visited[next_station]:
            visited[next_station] = True
            q.append((next_station, cnt + 1))

print(ans)

먼저 제일 처음 도전했던, 모든 간선들을 연결하는 풀이이다. 시간복잡도는 괜찮으나, 공간복잡도가 받쳐주지 못한다..

 

# 백준 5214 환승
import sys
from collections import deque

input = sys.stdin.readline
ans = -1

# N: 역 개수, K: 한 하이퍼튜브가 연결하는 역 수, M: 하이퍼튜브 개수
N, K, M = map(int, input().split())

# 역 방문 여부 기록
visited = [False for _ in range(N + 1)]

# 각 하이퍼튜브가 연결한 역 리스트 저장
loop_to_station = []

# 각 역이 연결된 하이퍼튜브 번호 리스트 저장
station_to_loop = [[] for _ in range(N + 1)]

# 하이퍼튜브별로 연결된 역 입력
for i in range(M):
    loop = list(map(int, input().split()))
    loop_to_station.append(loop)  # i번 하이퍼튜브가 연결한 역들

    # 각 역이 어떤 하이퍼튜브(i번)에 연결되어 있는지 저장
    for station in loop:
        station_to_loop[station].append(i)

# BFS 탐색 시작
q = deque()
visited[1] = True
q.append((1, 1))  # (현재 역, 방문 횟수)

while q:
    station, cnt = q.popleft()

    # 도착역이면 종료
    if station == N:
        ans = cnt
        break

    # 현재 역이 연결된 하이퍼튜브들을 순회
    for loop_num in station_to_loop[station]:
        # 해당 하이퍼튜브를 통해 도달할 수 있는 모든 역 탐색
        for next_station in loop_to_station[loop_num]:
            if not visited[next_station]:
                visited[next_station] = True
                q.append((next_station, cnt + 1))

print(ans)

역과 하이퍼루프를 구분하여 이분그래프처럼 구성하니 통과했다.

이렇게하니 python3로는 시간초과가 발생하여 pypy3로 통과하였다.

 

 

시간측면에서 좀 더 개선한 코드를 첨부한다.

 

import sys
from collections import deque

# N: 역 개수, K: 하이퍼튜브가 연결하는 역 개수, M: 하이퍼튜브 개수
N, K, M = map(int, sys.stdin.readline().split())

# 총 정점 수 = 역(N개) + 하이퍼튜브(M개)
# 역: 1 ~ N번, 하이퍼튜브: N+1 ~ N+M번 노드로 간주
lst = [[] for _ in range(N + M + 1)]

# 각 하이퍼튜브 정보를 입력받아 연결 리스트 구성
for i in range(M):
    hyper_nums = list(map(int, sys.stdin.readline().split()))

    # 하이퍼튜브 노드는 N+i+1번에 해당
    for hyper_num in hyper_nums:
        # 하이퍼튜브 ↔ 역 쌍방향 연결
        lst[N + i + 1].append(hyper_num)      # 하이퍼튜브 → 역
        lst[hyper_num].append(N + i + 1)      # 역 → 하이퍼튜브

# visited 배열: 방문 여부 + 해당 노드까지 도달하는 데 걸린 단계 수 저장
visited = [-1] * (N + M + 1)

# BFS 탐색 시작 (1번 역에서 출발)
q = deque([1])
visited[1] = 1  # 역에서 시작이므로 1로 초기화

while q:
    cur = q.popleft()
    for nxt in lst[cur]:
        if visited[nxt] == -1:
            # 아직 방문하지 않은 노드라면 큐에 추가
            q.append(nxt)
            # 이전 노드에서 +1한 거리 저장
            visited[nxt] = visited[cur] + 1

# 도착역 N번에 방문하지 못했다면 -1 출력
if visited[N] == -1:
    print(-1)
else:
    # 하이퍼튜브 노드와 역 노드를 오가며 진행했으므로,
    # 실제 역 방문 횟수는 (거리+1)//2 (역 → 하이퍼튜브 → 역 = 2단계 → 실제로는 1회 이동)
    print((visited[N] + 1) // 2)