문제
1번 회사에서 출발하여 k번 회사를 방문한 뒤에 x번 회사로 가는 것이 목표.
각 회사 간 시간은 1
최소 이동 시간은?
만약 x번 회사에 도달할 수 없다면, -1을 출력
-
테스트 케이스
-
5 7 # 회사 개수 n, 경로의 개수 m
1 2 # 연결된 두 회사의 번호
1 3
1 4
2 4
3 4
3 5
4 5
4 5 # x, k -
답: 3
-
4 2
1 3
2 4
3 4 -
답: -1
-
나의 풀이
1. 플로이드 워셜 알고리즘으로 풀이
import sys
input = sys.stdin.readline # 빠른 입력을 위해 설정
n, m = map(int, input().split()) # 회사(노드) 개수 n, 경로(간선) 개수 m
company = [list(map(int, input().split())) for _ in range(m)] # 각 회사별 연결된 회사 번호 list
x, k = map(int, input().split()) # 최종 목적지 x, 중간 목적지 k
INF = int(1e9) # 각 회사간 거리가 연결되어있지 않을 경우인 무한을 의미하는 값으로 10억 설정
# 회사들간 거리를 담을 2차원 list. 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 시간은 0으로 초기화
for i in range(1, n + 1): # 회사 개수가 n개 이므로, 1~n 범위 설정
graph[i][i] = 0
# 한 회사에서 연결된 다른 회사로 가는 시간 = 1로 초기화
# 양방향이므로, 서로에게 가는 경우를 설정
# i[0]: input에서 출발 회사. i[1]: 도착 회사
for i in company:
graph[i[0]][i[1]], graph[i[1]][i[0]] = 1, 1
# 플로이드 워셜 알고리즘 수행
# 점화식: D_ab = min(D_ab, D_ak + D_kb)
# a에서 b로 가는 시간 = a에서 b로 가는 최소 시간과 a에서 k를 거쳐 b로 가는 시간을 비교하여 더 작은 값으로 갱신
for k in range(1, n + 1): # 회사 개수가 n개 이므로, 1~n 범위 설정
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# 1에서 k를 거쳐 x로 가는 것이 불가능 할 경우(즉 초기에 설정한 INF가 남아있을 경우), -1 출력
if graph[1][k] == INF or graph[k][x] == INF:
print(-1)
else: # 가능할 경우, 1에서 k까지 가는 시간 + k에서 x까지 가는 시간 출력
print(graph[1][k] + graph[k][x])2. 개선된 다익스트라 알고리즘으로 풀이
import heapq
# ValueError: not enough values to unpack (expected 2, got 0) 오류 발생으로 인해
# sys.stdin.readline 을 사용하지 않음
n, m = map(int, input().split()) # 회사(노드) 개수 n, 경로(간선) 개수 m
company = [list(map(int, input().split())) for _ in range(m)] # 각 회사별 연결된 회사 번호 list
x, k = map(int, input().split()) # 최종 목적지 x, 중간 목적지 k
INF = int(1e9) # 각 회사간 거리가 연결되어있지 않을 경우인 무한을 의미하는 값으로 10억 설정
graph = [[] for _ in range(n + 1)] # 각 회사에 연결된 회사에 대한 정보를 담는 list
time = [INF] * (n + 1) # 최단 시간 테이블을 모두 무한으로 초기화
# 한 회사에서 연결된 다른 회사로 가는 시간 = 1로 초기화
# i[0]: input에서 출발 회사. i[1]: 도착 회사
# 양방향이므로, 서로에게 가는 경우를 설정
# 이때, 무조건 append 함수를 써야함!
for i in company:
graph[i[0]].append((i[1], 1))
graph[i[1]].append((i[0], 1))
def dijkstra(start, end):
q = []
# 시작 회사로 가기 위한 최단 시간 = 0으로 설정하여, 큐에 삽입
heapq.heappush(q, (0, start))
time[start] = 0
while q: # q가 비어있지 않다면, 반복
# 가장 최단 시간이 짧은 회사에 대한 정보 꺼내기
# t: 시간, now: 현재 회사
t, now = heapq.heappop(q)
# 현재 회사가 이미 처리된 적 있다면(즉 이미 최단 시간이라면), 무시
if time[now] < t:
continue
# 현재 회사와 연결된 다른 인접 회사들을 확인
for i in graph[now]:
cost = t + i[1]
# 현재 회사를 거쳐서, 다른 회사로 이동하는 시간이 더 짧은 경우
if cost < time[i[0]]:
time[i[0]] = cost # 더 짧은 시간으로 갱신
heapq.heappush(q, (cost, i[0])) # 큐에 삽입
return time[end]
# 1) 1에서 k까지 시간, k에서 x까지 시간 각각 구해서 더함
start_to_k = dijkstra(1, k) # start에서 k로 가는 최단 시간
time = [INF] * (n + 1) # 최단 시간 테이블을 모두 무한으로 초기화
k_to_x = dijkstra(k, x) # k에서 x로 가는 최단 시간
# start에서 k를 거쳐 x로 가는 것이 불가능 할 경우(즉 초기에 설정한 INF가 남아있을 경우), -1 출력
if start_to_k == INF or k_to_x == INF:
print(-1)
else: # 가능할 경우, 시간 출력
print(start_to_k + k_to_x): 진짜 99.9% 다 풀어놓고.. def 하나 더 만들어서 푼답시고 했다가 틀린답 나고..고생했다ㅠ 결국 def 하나 더 안 만들고 문제 해결.
- 마지막 부분 원래 풀이: start_k_x(start, k, x) 만들었으나..
왜 k에서 x까지 오답이 도출되는지 도통 모르겠다ㅠㅠ
# 2) start_k_x(start, k, x) 함수를 만들어서 구함
# 그러나.. 1에서 k까지 시간은 정상적으로 구해지는데, k에서 x까지는 틀린답 도출
# k에서 x까지의 시간 list를 출력해보니, 전체가 틀린 값임. 뭐가 잘못된걸까?
def start_k_x(start, k, x):
start_to_k = dijkstra(start, k) # start에서 k로 가는 최단 시간
time = [INF] * (n + 1) # 최단 시간 테이블을 모두 무한으로 초기화
k_to_x = dijkstra(k, x) # k에서 x로 가는 최단 시간
# start에서 k를 거쳐 x로 가는 것이 불가능 할 경우(즉 초기에 설정한 INF가 남아있을 경우), -1 출력
if start_to_k == INF or k_to_x == INF:
print(-1)
else: # 가능할 경우, 시간 출력
print(start_to_k + k_to_x)
# 1에서 k를 거쳐 x로 가는 최단 시간 출력(이동이 불가능 할 경우, -1 출력)
start_k_x(1, k, x)
내 인생의 주연