[Summer/Winter Coding(~2018) / 프로그래머스] 12978번 : 배달

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

 

Lv2 문제이고, 다익스트라 문제다!

다익스트라 몇 번 들어봤는데 정확한 알고리즘은 이제 공부한다 

다익스트라 알고리즘은 일반적인 그래프 탐색에서 heap 자료구조를 사용하는 알고리즘이라고 이해했다 

 

풀이 이해 

• 주어진 간선들을 노드 중심인 그래프로 변경한다 (graph 행렬)
• 1번 노드부터 해당 노드가지의 최소 거리를 저장하는 float('inf')로 이루어진 result 배열을 생성한다(이렇게 안 하면 몇몇 테스트에서 실패한다) 
  • 이때 1번 노드에서 1번 노드의 거리는 0이므로 result[1] = 0 으로 설정한다 (이렇게 안 하면 몇몇 테스트에서 실패한다)
• 현재 노드를 x, 이전 노드를 a라고 한다면 (a 노드에서 x 노드의 누적 값) < result[x] (그동안 x까지의 최소 거리) 라면, result[x]를 해당 값으로 변경해주고, 힙에 경로를 추가한다 
• result에서 K 이하인 원소들의 개수를 answer에 저장 후 반환한다 

 

- 정답 풀이 :

import heapq

def solution(N, road, K):
    graph = [[] for _ in range(N + 1)]
    result = [float('inf')] * (N + 1) # 거리 누적 값이 2001보다 클 수 있으므로 inf
    result[1] = 0 # 1번노드에서 1번 노드 거리는 0이다 
    
    for x, y, z in road:
        graph[x].append([y,z])
        graph[y].append([x,z])  
        
    queue = []
    heapq.heappush(queue,[1, 0]) # 노드 번호, 1번부터의 거리
    
    # dijkstra 함수 시작 
    while queue:
        a, b = heapq.heappop(queue)       
        for x,y in graph[a]:
            if b + y < result[x]:
                result[x] = b + y
                heapq.heappush(queue, [x, b + y]) 
    # 함수 끝 
                        
    answer = 0
    for i in range(1, len(result)):
        if result[i] <= K:
            answer += 1
            
    return answer

 

 

- 시도해본 풀이 : 

나름 그래프 구현한다고 해봤는데 잘 안 풀렸던 풀이다!

 

그래프 탐색을 위해 [노드번호, 1번부터 해당 노드까지의 거리]를 queue에 추가한다

result에는 1번부터 i번째 노드까지의 최소 길이들을 누적한다 

queue로 탐색하면서 방문하지 않은 노드를 탐색하고, 거리를 계산해서 result의 값을 바꿔준다 

전체 거리 중에 K이하인 원소의 갯수를 세서 반환한다 

 

 

정답 풀이와 비교하자면

queue는 순차적으로 탐색하는 것이 아닌 거리가 짧은 순서대로 탐색을 진행한다. 이를 위해 heapq를 사용한다 

visit 배열을 사용하지 않는다

def solution(N, road, K):
    graph = [[] for _ in range(N + 1)]
    for x, y, z in road:
        graph[x].append([y,z])
        graph[y].append([x,z])
        
    queue = [[1, 0]] # 노드 번호, 1번부터의 거리 
    result = [2001] * (N + 1)
    visit = [0] * (N + 1)
    visit[0], visit[1], result[1] = 1, 1, 0
    
    while queue:
        a, b = queue.pop(0)       
        for x,y in graph[a]:
            if not visit[x]:
                visit[x] = 1
                result[x] = min(result[x], b + y)
                queue.append([x, result[x]])
                
    answer = 0
    for i in range(1, len(result)):
        if result[i] <= K:
            answer += 1
            
    return answer