[PG/Python] 배달

📌 문제

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

코딩테스트 연습 - 배달

 

📌 문제 접근 방법

1. 다익스트라 알고리즘을 사용하였다.
2. 우선 각각의 노드간의 연결 관계를 인접행렬에 저장해주었다.
   연결 관계가 2개 이상인 경우도 있기에, 이미 값이 있다면 최소의 거리를 저장하도록 했다.
3. distance라는 리스트를 만들어서 여기에 해당 노드까지 가는 최소 거리를 저장하였다.
   항상 출발지는 1번 노드이므로 1번 노드의 distance는 0으로 초기화하였다.
4. 노드의 개수만큼 반복문을 돌리면서 방문하지 않은 노드 중에서 최소거리가 되는 노드를 찾는다.
5. 해당 노드를 방문 체크하고 거리를 갱신한다.
6. 반복문이 끝난 뒤, distance에 K보다 작거나 같은 값의 개수를 세어 answer에 저장 후 반환한다.

 

📌 코드

def solution(N, road, K):
    town = [[0 for _ in range(N+1)] for _ in range(N+1)]
    
    for s, e, d in road:
        if town[s][e]:
            town[s][e] = min(town[s][e], d)
            town[e][s] = min(town[e][s], d)
        else:
            town[s][e] = d
            town[e][s] = d
    
    visited = [0 for _ in range(N+1)]
    
    distance = [float('inf') for _ in range(N+1)]
    distance[1] = 0
    
    for _ in range(N):
        min_idx = -1
        min_val = float('inf')
        
        for i in range(1, N+1):
            if not visited[i] and distance[i] < min_val:
                min_idx = i
                min_val = distance[i]
        
        visited[min_idx] = 1
        
        for i in range(1, N+1):
            if town[min_idx][i] and not visited[i]:
                distance[i] = min(distance[i], distance[min_idx]+town[min_idx][i])
        
    answer = 0
    for d in distance[1:]:
        if d <= K:
            answer += 1
            
    return answer