프로그래머스 파이썬 가장 먼 노드

https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

https://pybeginner.tistory.com/89

프로그래머스 파이썬 배달

 

아주 그냥 똑같다

 

다만 다른점이라면 두번째로 큰 값을 어떻게 찾지? 라는 생각으로 검색을 좀 돌려봤는데

https://shoark7.github.io/programming/algorithm/second-largest-number-in-array

숫자 배열에서 두 번째로 큰 값 찾기

정말 생각의 깊이가 다르신 분이었다..

 

for문을 돌려서 계속 비교를하면 끝이긴했지만 거기서 좀 더 좋은 방향을 찾기위해서 트라이하시는 부분이 입이 쩍 벌어졌다.

 

import sys
import heapq

def solution(n, vertex):
    
    INF = sys.maxsize

    dp=[INF]*(n+1)

    heap =[]

    edge = [[] for i in range(n+1)]
    for i in vertex:
        edge[i[0]].append((1,i[1]))
        edge[i[1]].append((1,i[0]))

    def dijkstra(start):

        dp[start] = 0

        heapq.heappush(heap,(0,start))

        while heap:

            a, now = heapq.heappop(heap)

            if dp[now] < a:
                continue

            for w, node in edge[now]:

                next_a = w + a

                if next_a < dp[node]:

                    dp[node] = next_a

                    heapq.heappush(heap,(next_a,node))

    def second(arr):

        two = one = -float('inf')

        for n in arr:
            if n > one:
                two = one
                one = n
            elif two < n < one:
                two = n

        return two

    dijkstra(1)
    search = second(dp)
    return dp.count(search)

전 포스트와 거의 동일하니 설명은 생략함.