첫째 줄에는 한 칸씩의 공백을 두어 지역의 수와 한 지역에서 다른 지역으로 가는 총 방법의 수가 주어지며 두 번째 줄부터 m+1줄까지는 한 칸씩의 공백을 두어 각 지역과 그 지역에서 갈 수 있는 지역 그리고 그 지역으로 가는데 필요한 비용이 주어진다.
출력
첫째 줄에 S대학교를 가는데 드는 최소 비용을 출력한다. 만약 현호가 S대학교를 갈 수 없다면 "Impossible"를 첫째 줄에 출력한다.(단, 큰따옴표는 출력하지 않는다)
입력 예시
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40
출력 예시
149
풀이
*주의 : 이 문제는 불완전한 테스트케이스를 포함하고 있습니다!
요즘 문제 풀이를 올리는 기준에 대해 조금 고민이 많아졌다. 너무 쉬운 문제를 양산하듯 올리자니 전체적인 퀄리티를 떨어뜨리는것 같고, 그러지 않자니 포스팅하지 않는 날도 많아져서... 코드업이 테스트케이스를 제공해주는 장점이 있지만, 이런 문제 난이도에 대한 객관적인 rating이 부족한 게 아쉽다.
이 문제의 풀이부터 짚고 넘어가자면, 단순히 0을 시작점, 1을 끝점으로 하는 다익스트라 알고리즘을 적용해 주면 된다. 파이썬의 메모리 제한을 고려하자면 dist값을 저장하는 경우 2차원 리스트 대신 딕셔너리를 사용하는게 더 효율적이며(n값에 비해 m값이 매우 작다. n의 제곱의 경우의 수가 나올 수 있지만 m값은 100000 이하기 때문이다), 최소 경로를 구하고 싶으므로 두 노드 사이에 여러 경로가 존재한다면 그 중 최소값만을 저장하면 된다.
문제는 다음 테스트케이스다 :
잘못된 테스트케이스
이 경우는 입력 자체가 올바르지 않은 경우이다. 둘째 줄부터 m+1개의 줄에는 세 정수가 와야 하기 때문. 일반적인 풀이로는 절대 정답을 맞출 수 없다. 따라서 이러한 상황에 대한 예외 처리를 해주는 편법이 필요하다. 파이썬의 경우 try except문으로 우선 해결했다.
풀이 코드
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
try :
n, m = map(int, input().split())
MAX = float('inf')
dist_dict = { key : dict() for key in range(n)}
dist_list = [MAX]*n
for _ in range(m) :
a, b, c = map(int, input().split())
if a-1 not in dist_dict[b-1] or dist_dict[b-1][a-1] > c :
dist_dict[b-1][a-1] = dist_dict[a-1][b-1] = c
q = [(0,0)]
while q :
cost, node = heappop(q)
if node == m-1 or dist_list[node] <= cost :
continue
dist_list[node] = cost
for _node, _cost in dist_dict[node].items() :
if _node != node :
next_cost = cost + _cost
if dist_list[_node] > next_cost :
heappush(q, (next_cost, _node))
print(dist_list[-1] if dist_list[-1] < MAX else'Impossible')
except :
print('Impossible')
