문제 설명 및 제한사항
아이디어 및 해결 방법
코드
from queue import PriorityQueue
from collections import defaultdict
from math import inf
def solution(N, road, K):
# 다익스트라로 해결합니다.
A = defaultdict(list)
for u, v, w in road:
A[u].append((v, w))
A[v].append((u, w))
# 두 마을을 잇는 도로를 짧은 도로 순으로 정렬합니다.
for k, v in A.items():
A[k] = list(sorted(v, key=lambda tup: tup[1]))
dist = [inf] + [0] + [inf] * (N-1)
vis = [True] + [False] * N
q = PriorityQueue()
q.put((0, 1))
vis[1] = True
while not q.empty():
_, u = q.get()
for v, w in A[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
q.put((dist[v], v))
vis[v] = True
return sum([x <= K for x in dist])
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges