[프로그래머스/Python] Level 2_배달 (Summer/Winter Coding(~2018))

📌문제 유형

Summer/Winter Coding(~2018) (다익스트라)

 

📌문제

프로그래머스

 

📌나의 문제풀이

- 다익스트라 표 만들어서 최소값 넣기

(단, 1은 0시간 걸리므로 1은 반드시 포함하기)

- 같은 마을을 건너지만 거리가 다를 수 있으므로 이거에 대한 최소값 넣기

def solution(N, road, K):
    answer = 1
    inf = 1e9
    graphs = [[inf for _ in range(N+1)] for _ in range(N+1)]
    
    # 아동 시간 중 최소값 넣기
    for a,b,c in road:
        graphs[a][b] = min(graphs[a][b],c)
        graphs[b][a] = min(graphs[b][a],c)
        
    # 다익스트라    
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                graphs[i][j] = min(graphs[i][j], graphs[i][k] + graphs[k][j])
        
    # 1은 0시간 걸리니까 반드시 포함하기
    for l in range(len(graphs[1])):
        if l == 1:
            continue
        else:
            if graphs[1][l] <= K:
                answer += 1
            
    return answer

 

📌다른 사람의 문제풀이

- 1에서만 출발하기 때문에, 1에 대한 다익스트라만 적용

- heaqp를 활용하여 최단 거리에 대한 값을 꺼내서 갱신 가능

import heapq

def dijkstra(dist,adj):
    # 출발노드를 기준으로 각 노드들의 최소비용 탐색
    heap = []
    heapq.heappush(heap, [0,1])  # 거리,노드
    while heap:
        cost, node = heapq.heappop(heap)
        for c,n in adj[node]:
            if cost+c < dist[n]:
                dist[n] = cost+c
                heapq.heappush(heap, [cost+c,n])


def solution(N, road, K):
    dist = [float('inf')]*(N+1)  # dist 배열 만들고 최소거리 갱신할거임
    dist[1] = 0  # 1번은 자기자신이니까 거리 0
    adj = [[] for _ in range(N+1)]  # 인접노드&거리 기록할 배열
    for r in road:
        adj[r[0]].append([r[2],r[1]])
        adj[r[1]].append([r[2],r[0]])
    dijkstra(dist,adj)
    return len([i for i in dist if i <=K])

 

 

📌리뷰

- 최단거리라면 다익스트라 사용해보기