[TIL] day5

TIL

프로그래머스에서 준비한 코딩테스트 문제를 더 풀어봤는데,
두번째 테스트에서 다익스트라 알고리즘을 이용해야한다는 것까지는 생각이 들었지만 이제 이걸 응용을 못함..
나중에 따로 풀이법을 찾아보니 양방향으로 받아서 풀어야할필요가 있었던것같다.
(내 코드는 그냥 다익스트라 알고리즘 ctrl+C/ctrl+V 했던거임..🤯)

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def solution(N, road, K):
    start = 1
    graph = [[] for i in range(N+1)]
    distance = [INF] * (N+1)

    for r in road:
        a, b, c = r
        graph[a].append((b,c))

    def dijkstra(start):
        q = []
        heapq.heappush(q, (0,start))
        distance[start] = 0
        while q:
            dist, now = heapq.heappop(q)
            if distance[now] < dist:
                continue
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))

    dijkstra(start)

    lst = []
    for d in distance:
        if d <= K:
            lst.append(d)

    return len(lst)

#진짜 다익스트라 코드 복붙이네

이것이 취업을 위한 코딩테스트다 with 파이썬(저.나동빈) 참고

다시 풀어봐야지