(Python/LV2) 배달

문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

풀이:

 

import heapq
def solution(N, road, K):

    graph = [[] for _ in range(N+1)]

    for i in range(len(road)):
        u, v, w = road[i]
        graph[u].append((v, w))
        graph[v].append((u,w)) # 양 방향 이기 때문

    dist = [float("inf") for _ in range(N+1)]
    dist[1] = 0
    print(dist)
    hq = []
    heapq.heappush(hq,(0,1))
    while hq:
        cur_w,cur_node = heapq.heappop(hq)
        for to_node, to_w in graph[cur_node]:
            dis = cur_w + to_w
            if dis < dist[to_node] :
                dist[to_node]  = dis
                heapq.heappush(hq,(dis,to_node) )

    count = 0
    for i in dist[1:]:
        if i <= K:
            count += 1
    return count


print(solution(5, [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]], 3))

 

백준에 있는 골드 문제와 거의 똑같다

 

 

graph = [[] for _ in range(N+1)]

for i in range(len(road)):
    u, v, w = road[i]
    graph[u].append((v, w))
    graph[v].append((u,w)) # 양 방향 이기 때문

dist = [float("inf") for _ in range(N+1)]
dist[1] = 0



[[], [(2, 1), (4, 2)], [(1, 1), (3, 3), (5, 2)], [(2, 3), (5, 1)], [(1, 2), (5, 2)], [(2, 2), (3, 1), (4, 2)]]
[inf, 0, inf, inf, inf, inf]

일단 그래프를 만들어서 그래프에 간선지와 가중치를 넣는다.

dist 에는 간선지 까지 드는 가중치중 최솟값을 넣어야하니 일단 최댓값인 inf 로 통일

 

0에서 0 은 없고

1에서 2는 1점 >>(2,1) 1에서 4는 2점(4,2) 

2에서 1은 1점 >> (1,1) 2에서3은 3점(3,3) ,,, 이런식으로 

 

그리고 dist[1] 에는 0 을 넣는다 시작점이기때문

 

 

hq = []
heapq.heappush(hq,(0,1))

최솟값을 쓰려면 heapq 를 써서 맨 위(리스트 맨앞)에 최솟값을 올린다 
그리고 hq 에 가중치와, 시작점을 넣어줌

 

 

 

while hq:
    cur_w, cur_node = heapq.heappop(hq) # cur_w 가중치, cur_node 시작점
    for to_node, to_w in graph[cur_node]: # to_node 목적지, to_w 가중치 값
        dis = cur_w + to_w # 새로운 가중치는 cur_w + to_w
        if dis < dist[to_node]: # 기존것과 비교해서 작으면
            dist[to_node] = dis # 작은걸로 최신화
            heapq.heappush(hq,(dis,to_node))  # 다시 가중치와, 시작지 최신화

 

이 부분이 가장 어려운 부분인데 내가 이해한 대로 작성해보겠다..

 

일단 hq 에 들어간 처음 (0,1) 을 꺼내준다

그러면 포문에서는 그래프[1] 1에서 [(2, 1), (4, 2)] 두개가 뽑아 두개를 돌면서

그럼 to_node 와 to_w 에 그 다음 간선지와, 가중치가 들어가게된다.

 

 

현재 가중치는 0점이고 , 1>>2가는건 1점, 1>>4 는 2점이  dis(가중치) 이다

dis(1점, 4점이) dist[2와 4] 에 있는 값보다 작으면 dis 와 다음 목적지인 to_node 를 넘기면서

 

가중치와, 도착지인 노드를 hq에 푸쉬해준다.

 

쭉 돌면서 완성해주면 최솟값만 남는다.

 

 

https://windy7271.tistory.com/entry/Python%F0%9F%8F%854%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1753%EB%B2%88-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C