[Python] 백준 18223번 : 민준이와 마산 그리고 건우

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

18223번: 민준이와 마산 그리고 건우

---

💡 문제 풀이

다익스트라 알고리즘 문제이다.

 

문제를 처음 읽으면 최단 경로에 건우가 있는지 따져야 할 것만 같지만 이 문제는 단순히 최소 비용만 따지면 된다.

마산까지의 최소 비용과 (시작 지점부터 건우가 있는 곳까지의 비용 + 건우가 있는 곳부터 마산까지의 비용)이 같다면

최단 경로의 길이보다 길어지지 않는 것이므로 건우를 구해서 마산으로 가도 괜찮다는 뜻이다.

구현한 다익스트라 함수로 최소 거리를 따져주면 된다.

✔️ 느낀 점

알고리즘을 잘 이해하고 문제에서 요구하는 점을 잘 따져주면 쉽게 풀 수 있는 문제이다.

💻 코드

import sys, heapq
input = sys.stdin.readline
INF = int(1e9)

V, E, P = map(int, input().split())
graph = [[] for _ in range(V+1)]

for _ in range(E):
    start, end, cost = map(int, input().split())
    graph[start].append([cost, end])
    graph[end].append([cost, start])

def dijkstra(start):
    distances = [INF] * (V+1)
    distances[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    
    while q:
        currentCost, currentNode = heapq.heappop(q)
        
        if distances[currentNode] < currentCost: continue
        
        for nextCost, nextNode in graph[currentNode]:
            newCost = nextCost + currentCost
            if newCost < distances[nextNode]:
                distances[nextNode] = newCost
                heapq.heappush(q, [newCost, nextNode])
    
    return distances

print("SAVE HIM" if dijkstra(1)[V] == (dijkstra(1)[P] + dijkstra(P)[V]) else "GOOD BYE")