[프로그래머스] 배달

https://programmers.co.kr/learn/courses/30/lessons/12978#

코딩테스트 연습 - 배달

 

<코드>

def solution(N, road, K):
    cnt = 1
    INF = 500001
    adj = [[INF]*(N+1) for _ in range(N+1)]
    for food in road:
        s, e = food[0], food[1]
        if adj[s][e] > food[2]: # 이미 있는 길보다 적은 시간이 걸릴 경우
            adj[s][e] = food[2]
            adj[e][s] = food[2]                 
    
    hour = adj[1][:] # 1번 가게에서 직항으로 가는 가게들 걸리는 시간
    U = {1} # 방문한 가게들
    while len(U) < N+1:
        min_val = INF
        min_idx = 0
        
        for i in range(2, N+1): # 2번부터 N번까지의 가게 중에 가장 거리가 짧은 가게 찾는다
            if i not in U and hour[i] < min_val:
                min_val = hour[i]
                min_idx = i
        U.add(min_idx) # 방문한 가게에 넣어준다
        
        for j in range(2, N+1): # 1 -> A가게 보다 1-> 가장 짧은 가게 -> A가게가 더 짧을 경우 업데이트
            if j not in U and hour[min_idx] + adj[min_idx][j] < hour[j]:
                hour[j] = hour[min_idx] + adj[min_idx][j]
    
    for h in hour:
        if h <= K:
            cnt += 1
    
    return cnt

 

<풀이방법>

1. prim알고리즘으로 풀었는데 1번 가게에서 갈 수 있는 가장 짧은 거리를 갈 수 있는 가게를 찾는다.

2. 방문한 가게에 넣어주고 1번에서 A라는 가게를 갈 수 있는 경우보다 1번에서 가장 짧은 거리의 가게를 들렸다가 A라는 가게를 가는 경우가 더 짧을 경우 업데이트 해준다.

 

<리뷰>

prim 기억에서 사라지고 있었는데 다시 한번 문제를 풀면서 기억을 되살렸다.

여러 방법으로 풀 수 있는 문제라고 생각한다.