[BOJ/PYTHON] 18223. 민준이와 마산 그리고 건우 (최단 경로 - 다익스트라)

백준 문제 링크: https://www.acmicpc.net/problem/18223

문제 요약

마산(도착지, v번 정점)이 더 가까우면 그냥 마산으로, 최단 경로에 건우가 있으면 겸사겸사 구해줌

민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력

핵심 아이디어

그래프 간선에 가중치가 있고, 가중치가 양수이기 때문에 다익스트라 알고리즘을 사용하면 된다.

이때, 건우를 구해준 후 마저 마산까지 가는 거리가 최단경로보다 길어지지 않으면 건우를 구하는 거라 건우를 구하러까지 가는 최단 거리, 구하고 나서 마산까지 가는 최단 거리, 출발지에서 마산까지 직통으로 가는 최단 거리값들이 필요하다.

풀이

# gold4-18223. 민준이와 마산 그리고 건우

import sys, heapq
input = sys.stdin.readline

v, e, p = map(int, input().split()) # 정점 개수, 간선 개수, 건우가 위치한 정점
graph = [[] for _ in range(v + 1)]
for _ in range(e):
    a, b, c = map(int, input().split()) # a번 정점과 b번 정점 사이의 거리가 c
    # 양방향 그래프
    graph[a].append((b, c))
    graph[b].append((a, c))
INF = int(1e9)

# 마산(도착지, v번 정점)이 더 가까우면 그냥 마산으로, 최단 경로에 건우가 있으면 겸사겸사 구해줌
# 민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력

def dijkstra(start, end):
    distance = [INF]*(v+1)
    q = []
    heapq.heappush(q, (0, start)) # 시작점: 거리 0, 시작노드
    distance[start] = 0 # 자기자신 방문한 거리는 0
    while q:
        dist, now = heapq.heappop(q) # 최단 거리, 최단 거리의 노드
        # 이번에 볼 거리인 dist가 지금까지 갱신된 최단거리인 distance[now]보다 작으면 이미 본 거니까 더 볼 가치가 없음.
        if distance[now] < dist: continue 
        for next, next_dist in graph[now]:
            cost = dist + next_dist # 비용: 지금 노드까지의 거리 + 다음 노드까지의 거리
            # 이번 노드에서 다음 노드까지 거쳐 가는 게 이번 노드 없이 건너뛰어서 다음 노드까지 가는 거리보다 더 짧으면
            if cost < distance[next]: 
                distance[next] = cost # 더 짧은 거리(이번 노드 거쳐가는 거리)로 갱신해줌
                heapq.heappush(q, (cost, next)) # 여기도 갱신
    return distance[end] # 목표 지점까지의 최단 거리

if dijkstra(1, p) + dijkstra(p, v) <= dijkstra(1, v): # 건우 구해주는 경로 길이가 마산까지 가는 최단경로보다 짧거나 최단경로에 있으면
    print("SAVE HIM") # 겸사겸사 구해줌
else: # 마산이 더 가까워서 건우 버림
    print("GOOD BYE")

Trouble Shooting

우선 ‘양방향 그래프’라는 문제 조건을 누락해서 입력 받을 때 단방향 그래프로만 처리해서 이후 양방향 그래프로 고쳤다.

처음에는 시작점인 1을 기준으로 다익스트라 함수를 한 번 돌리고 그거에 대해서 건우를 구해주는 거리랑 마산까지 가는 최단거리만 비교했다.

distance[p] <= distance[v] 이면 print("SAVE HIM")이라고 생각했는데 문제 자체가 건우를 구해주고 끝내는 게 아니라 구해주고 마산까지 가야 하는 거였다.

또한, 구해준 후에도 건우를 구해준 지점 기준으로 마산까지 최소 거리로 가야 해서 함수에 start값만 받던 거를 end값까지 받고 최단거리를 return하는 방식으로 바꿨다.

실행 시간

메모리 36396KB, 시간 88ms (python3)