[백준 18223번] 파이썬 - 민준이와 마산 그리고 건우

백준 18223 - 민준이와 마산 그리고 건우

시간 제한 1초, 메모리 제한 256MB

# 조건

• 먼저 고향으로 내려갔던 친구인 건우에게 연락이 왔다.

• 건우는 고향으로 내려가던 중 알 수 없는 일에 휘말려 외딴곳에 혼자 남겨지게 되었다.

• 건우는 유일한 구세주인 민준이에게 도움을 청한 것이었다.

• 그러나 마산의 남자인 민준이에게는 마산이 먼저였다.

• 민준이는 처량한 건우를 무시한 채 고향으로 떠나려고 했지만, 만약 고향으로 가는 길에 건우가 있다면 겸사겸사 도움을 줄 수 있을 것 같았다.

• 지도는 양방향 그래프 형태로 되어있다.

  • 출발지는 1번 정점 마산은 V번 정점이다.
  • 정점은 1~V까지 있다.
  • 건우는 P번 정점에 있다.

• 그리고 항상 1번 정점에서 P번과 V번 정점으로 갈 수 있는 경로가 존재한다.

• 중복되는 간선과 자기 자신을 가리키는 간선은 존재하지 않는다.

• 아래와 같은 그래프가 있을 때,

• 위의 경우는 최단 경로가 두 가지 있다.
  • 1→3→4→5→6 또는 1→3→5→6 이다.
  • 이것 중에서 건우가 있는 곳, 즉 4번 정점이 포함된 최단 경로가 있으므로 이 경우에는 민준이가 건우를 도울 수 있다.
• 민준이가 건우를 도와주는 경로의 길이가 최단 경로의 길이보다 길어지지 않는다면, 민준이는 반드시 건우를 도와주러 간다.
• 어쩌면 지킬 수도 있는 민준이의 우정을 위해 우리가 도와주자!

입력

• 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V)
• 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 a,b,c가 공백으로 구분되어 주어진다.
• 이는 a번 정점과 b번 정점 사이의 거리가 c임을 의미한다. (1 ≤ a,b ≤ V, 1 ≤ c ≤ 10,000)

출력

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

# 접근 방법

• 다익스트라를 이용하였다.
• 경로를 기록할 graph, 이동 거리를 기록할 dist 배열을 v+1의 크기로 생성해준다.
• 입력받는 경로를 양방향으로 기록 해준 후 다익스트라를 수행할건데, 이 때 1번 => 출발지가 건우가 있는 곳이라면 바로 SAVE HIM을 출력해준다.
• 다익스트라에 사용될 q에는 [현재 이동거리, 노드 번호, 건우 구출 여부]를 최소힙으로 구성해준다.
• heappop을 하여 val, node, visit 변수에 할당해준 후, 만약 dist[node]가 이미 val => 이동 거리가 더 짧은 경로가 존재한다면 continue를 해준다.
• 또한 V => 마산에 도착하였다면 2가지를 확인해주는데, 현재의 값이 기록되어 있는 최소 경로보다 크다면 종료해준다.
  • => 이유는 heap에 넣기 전 미리 경로의 값을 구하기 때문에, 도착점에서 min_value보다 크다면 이후에는 최적의 경로가 더 이상 나올 수 없기 때문이다.
  • 또한, visit == 1인 경우 => 건우를 구출하였다면 바로 SAVE HIM을 출력해주면 되지만,
  • 아닌 경우 => min_value만 min(min_value, val)을 통해 갱신해준다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from heapq import heappush, heappop

def dijkstra():
    min_value = float('inf')
    q = []
    result = "GOOD BYE"
    heappush(q, [0, 1, 0])
    dist[1] = 0
    while q:
        val, node, visit = heappop(q)
        if dist[node] < val:
            continue
        if node == V:
            if val > min_value:
                return result
            else:
                if visit:
                    result = "SAVE HIM"
                    return result
                min_value = min(min_value, val)
                continue

        for i, j in graph[node]:
            n_val = j + val
            if dist[i] < n_val:
                continue
            if i == P:
                heappush(q, [n_val, i, 1])
            else:
                heappush(q, [n_val, i, visit])
            dist[i] = n_val

    return result

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

for _ in range(E):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

if P == 1:
    print('SAVE HIM')
else:
    print(dijkstra())