[Level 3] 배달

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

프로그래머스

▶ (참조)다익스트라 알고리즘 설명 (동빈나 유튜브) : https://www.youtube.com/watch?v=611B-9zk2o4

▶ (참조)다익스트라 알고리즘 원리, 코딩 (동빈나 블로그) : http://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234424646&categoryNo=128&parentCategoryNo=0&viewDate=¤tPage=5&postListTopCurrentPage=&from=postList

23. 다익스트라(Dijkstra) 알고리즘

▶ 코드 ( 다익스트라 알고리즘 : 선형탐색 ver. (시간복잡도 O(n^2) )

# 다익스트라 알고리즘 : 선형탐색 ver. (시간복잡도 O(n^2))
# 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있습니다.
# <과정> 
# 1. 출발 노드를 설정합니다
# 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다.
# 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택합니다.
# 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신합니다.
# 위 과정에서 3~4번을 반복합니다.

INF = 987654321

# dist배열 중, 방문하지 않았으면서 가장 작은 값 가진 정점 골라내기  
def getSmallDistIndex(dist, N):
    min_value = INF
    index = 0
    for i in range(N+1):
        if dist[i] < min_value and visited[i] == 0:
            min_value = dist[i]
            index = i
    return index

# 코딩편의를 위해, '이차원 배열' 형태로 만들어준다.
def normalize(road, N):
    t = [[0 for i in range(N+1)] for i in range(N+1)] 
    
    for a in road:
        if t[a[0]][a[1]] != 0:  # 이미 있는 경로일때 
            if a[2] < t[a[0]][a[1]]:    # 비교해서 더 작으면..갱신해주기 
                t[a[0]][a[1]] = a[2]
                t[a[1]][a[0]] = a[2]    # 양방향으로 넣어줘야됨 
        else:
            t[a[0]][a[1]] = a[2]
            t[a[1]][a[0]] = a[2]  
    return t

def dijkstra(road, N):
    global visited

    road = normalize(road, N)
    #print('road=', road)
    
    visited = [0]*(N+1)
    dist = [INF for i in range(N+1)]

    # 1번 정점에서 출발
    dist[1] = 0 
    visited[1] = 1
    for i in range(N+1):
        if road[1][i] != 0:
            dist[i] = road[1][i]    # 1번 정점이랑 인접한 정점들의 가중치 넣어줌 
    #print('시작 dist=', dist)
    #print()

    for _ in range(N-1): # 총 N-1번 반복(=1번 정점 제외)
        current = getSmallDistIndex(dist, N) # 현재 기준 (=거쳐서 갈 정점)
        #print('current index=',current)
        visited[current] = 1                 # current를 방문처리 
        #print('현재 visited=', visited)
        
        for j in range(1, N+1): # 1,2,,,,N
            if visited[j] == 0 and road[current][j]!=0 :    # 방문하지 않았으면서 길이 있는 경우 
                if dist[current] + road[current][j] < dist[j]:
                    dist[j] = dist[current] + road[current][j] # 최소값으로 갱신
        #print(dist)
        #print()
    return dist

def solution(N, road, K): # N=정점의 개수, K는 배달시간 최대허용치 
    answer = 0
    dist = dijkstra(road, N)
    #print(dist)
    for d in dist:
        if d <= K:
            answer += 1
    #print(answer)
    return answer

#solution(5,[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]],3)
#solution(6,[[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]],4) 

 

▶ 코드 ( 다익스트라 알고리즘 : 우선순위 큐 ver. (시간복잡도 O(n*(log(n))) )

# https://tttuer.tistory.com/169