[프로그래머스 lv3] 배달

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

프로그래머스

 

문제설명

 

링크 참고

 

 

문제 해결 방법

 

다익스트라알고리즘을 적용해 문제를 해결하였음

 

 

 

코드 구현

 

def solution(N, road, K):
    answer = 0
    
    distances = [float("inf")] * (N+1) 
    distances[0] = 0 # 0과 1은 사용하지 않음
    distances[1] = 0
    
    
    for i in range(N-1):
        for i in range(1, N+1):
            for nodeSet in road:
                fromm, to, weight = nodeSet
                if fromm == i:
                    distance = distances[i] + weight
                    if distance < distances[to]:
                        distances[to] = distance

                to, fromm, weight = nodeSet
                if fromm == i:
                    distance = distances[i] + weight
                    if distance < distances[to]:
                        distances[to] = distance
                    

    # N개의 마을 중에서 K시간 이하로 배달이 가능한 마을에서만 주문을 받으려고함
    # 1번 마을에 있는 음식점이 음식 주문을 받을 수 있는 마을의 개수를 return 
    
    # a, b = 마을의 번호 c = 도로를 지나는데 걸리는 시간
    
    # 그래프 만들기 
    answer +=1
    for i in distances:
        if i <= K and i>0:
            answer+=1
    
    return answer

 

 

 

시간/공간 복잡도

O((N+E)N)

 

최적화 및 개선

하지않음... 

 

 

어려웠던 점

 

양방향 이동이라는 점을 잘 새겨봤어야 했다. 코드를 짜다보니 나도 모르게 단방향으로 코드를 작성했다. 

다익스트라 알고리즘은 n-1번 반복해야 하는 것을 잘 기억해야겠다. 

처음에 코드 작성후, 채점하니 40점이 나왔는데 혹시나 해서 최단거리 구하는 코드를 한번더 복사 붙여넣기 한 후 채점하니 50점이 나왔다. 그 후 힌트를 얻기위해 책을 한번더 보고, 그 후 한번 더 복사 붙여넣기 하니 80점이 나왔는데 그때 깨달았다..