HackerRank / Jack goes to Rapture / Python

https://www.hackerrank.com/challenges/jack-goes-to-rapture/problem?isFullScreen=true 

Jack goes to Rapture | HackerRank

참조 <defaultdict>

https://dongdongfather.tistory.com/69

[파이썬 기초] 유사 딕셔너리 defaultdict() 활용법

참조 <heapq>

https://docs.python.org/ko/3/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.10.1 문서

해당 문제는 주어진 그래프에서 1번 노드에서 g_nodes까지 최소 금액으로 가는 길을 찾는것이다.

만약, 1번 노드에서 g_nodes까지 가는 길이 없을 경우 'NO PATH EXISTS'를 표시한다.

 

import math
import os
import random
import re
import sys

from collections import *
from heapq import *
n,m = map(int,input().split())
graph ={}
for i in range(m): # 양방향에 대한 정보를 저장한다.
    a,b,c = map(int,input().split())
    if a not in graph:
        graph[a] = [(b,c)]
    else:
        graph[a].append((b,c))
    if b not in graph:
        graph[b] = [(a,c)]
    else:
        graph[b].append((a,c))

cost = [float('inf')]*(n+1)
cost[1] = 0 
h = [(0,1)]
visited = [0]*(n+1)

while h :
    a,b = heappop(h) # heap에서 가장 작은 항목을 팝하고 반환한다.
    if visited[b]: # 상수는 0일때 False이며 0이 아닌 수는 True이다.
        continue   # 즉, 뒤로 돌아가는걸 막을수 있다.
    visited[b] = 1
    for x, y in graph[b]:
        if cost[x] > a + max(0,y - a): # 작은 값을 갖는 루트로 변경한다.
            cost[x] = a + max(0,y - a)
            heappush(h,(cost[x],x)) # (cost[x],x)를 h에 푸시한다.
            
if cost[-1] != float('inf'):
    print(cost[-1])
else:
    print('NO PATH EXISTS')

 

여기서 graph를 생성하는 부분을 defaultdict를 사용하여 코드를 줄일 수 있다.

graph = defaultdict(list)
for i in range(m):
	a,b,c = map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))
print(graph)