백준 1504 특정한 최단 거리 파이썬 풀이, 반례

난이도 : 골드4

풀이일 : 2401195

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

1504번: 특정한 최단 경로

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys, heapq

def djikstra(start, end):
    visited = [int(1e9) for _ in range(N + 1)]
    visited[start] = 0
    queue = []
    heapq.heappush(queue, [0, start])

    while queue:
        cost, now = heapq.heappop(queue)

        if cost <= visited[now]:
            for add, next in load[now]:
                if visited[next] > cost + add:
                    visited[next] = cost + add
                    heapq.heappush(queue, [cost + add, next])

    return visited[end]


N, E = list(map(int, sys.stdin.readline().split()))
load = [[] for _ in range(N + 1)]

for _ in range(E):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    load[a].append([c, b])
    load[b].append([c, a])

v1, v2 = list(map(int, sys.stdin.readline().split()))

sol1 = djikstra(1, v1) + djikstra(v1, v2) + djikstra(v2, N)
sol2 = djikstra(1, v2) + djikstra(v2, v1) + djikstra(v1, N)

if sol1 >= int(1e9) and sol2 >= int(1e9):
    print(-1)
else:
    print(min(sol1, sol2))

코드 구성

• 지나야 하는 정점 두 개 방문 순서를 다르게 하여 두 번 길을 탐색
  • 1 -> v1 -> v2 -> N or 1 -> v2 -> v1 -> N 두 가지 방법 가능
• 탐색은 다익스트라 알고리즘을 사용
• 두 길 탐색 중 작은 것을 출력하고, 길이 없을 때에는 -1을 출력

---

반례

입력	2 0 1 2
출력	-1

---

느낀점

• visited를 boolean 배열로 사용하려다가 틀렸다.
• 그 후에는 또 길이 없는 경우를 처리하지 않아서 틀리고.
• 그 후에는 마지막 if 문에서 등호를 넣어주지 않아서 틀렸다.
• 맨날 약속 시간 직전에 급하게 푸니까 자꾸 이런 것들을 실수하게 되는 것 같다. 오전에 푸는 습관을 좀 들이던지 열두시 넘은 새벽에 푸는 습관을 들이던지 해야겠다.