[그래프]백준_최소비용 구하기_1916(Dijkstra algorithm)

• 알고리즘 유형 : Dijkstra algorithm
• 풀이 참고 : 동기
• 문제 링크 : https://www.acmicpc.net/problem/1916

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사드리겠습니다. 

---

Dijkstra Algorithm

1. 간단 정리

  - 상세한 이론내용같은 부분은 다른 블로그를 참고하면 좋을 것 같고, 간단하게 내가 이해한 내용만 정리하려 한다.

  1) distance 체크

    - 노드별로 가중치를 기록한다. 기본값은 무한대(파이썬: inf)로 세팅하고 새로 받는 값들과 계속 비교하며 업데이트

    - distance 값을 계속적으로 최소값으로 만드는 행위를 relax 한다고 한다. 

    - 예) 4번 노드를 relax 한다.

  2) predecessor 체크

    - 최단경로에서의 직전 부모노드를 체크한다. 사용할 때도 있고 필요 없을 때도 있다. 

    - 사용하는 용도는 해당 데이터로 최단 경로의 노드를 나열 할 수 있다. (백트래킹 사용)

  3) complete 체크

    - 모든 인접 노드를 relax 하면 체크

 

2. 알고리즘의 전체적인 흐름

  1) 시작 노드가 필요하고 시작 노드의 가중치를 distance 체크

  2) 인접 노드들을 가중치가 적은 순으로 relax 한다.

  3) 모든 인접 노드를 relax 하면 relax한 노드들부터 다시 1번 시작

 

---

풀이 요약

1. 해당 문제는 최소비용만 구하면 되는 문제로 predecessor는 필요 없다.

2. Dijkstra 를 사용하는 기본 문제다. 

3. 그치만 난 못 풀었다. 어렵다.

4. 키포인트

  1) 처음 그래프를 받을때 sort()을 사용하지 않고 heappush로 받으면 자동으로 오름차순 정렬이 된다.(개꿀팁)

  2) complete 체크 위치가 중요하다. 잘못 체크하면 시간 초과가 난다. 

  3) 힙큐를 사용한다. 

  4) 릴랙스는 방문을 했던 안 했던 해주어야 한다. (조금 이해가 안 된다.)

  5) 반복하기 전 push 할 때 현재 distance 값을 넘겨야 한다. 

---

코드(python)

from cmath import inf
import sys, heapq
sys.stdin = open("input.txt","r")
# 15. https://www.acmicpc.net/problem/1916 : 최소비용 구하기

# n: 노드의 개수, m: 엣지 개수
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

# 그래프 받기
graph = [[] for _ in range(n+1)]
for i in range(1, m+1):
    a, b, cost = map(int, sys.stdin.readline().split())
    heapq.heappush(graph[a], (cost, b)) # 솔트를 안해도됨

# 시작 노드, 목표 노드
start, end = map(int, sys.stdin.readline().split())

# 방문 체크
complete = [False] * (n+1)
# 최소 가중치 체크 
distance = [inf] * (n+1)

def bfs(start, end):
    queue = [] # 힙큐 할 리스트
    distance[start] = 0 # 시작 노드는 가중치 0
    heapq.heappush(queue, (0, start)) # 힙푸쉬를 가중치와 노드값을 같이 넣음
    while queue:
        d, x = heapq.heappop(queue) # 큐에서 팝할때 가중치와 노드값을 따로 뺌
        complete[x] = True # 우선 방문 체크
        for i, j in graph[x]: # pop한 노드 기준으로 연결된 노드들 릴랙스
            if distance[j] > distance[x]+i: # 현 디스탠스가 pop한 노드의 가중치 + 릴랙스할려는 노드가중치 보다 클때
                distance[j] = distance[x]+i # 기존 가중치를 업데이트
            if complete[j] == False: # 방문 안한 노드라면
                complete[j] = True # 방문 처리
                heapq.heappush(queue, (distance[j],j)) # 디스탠스의 가중치와 노드값을 다시 push
    print(distance[end])

bfs(start, end) # (1)

---

배운 점, 배울 점

1. 힙 큐를 저번 주에 공부를 못하고 넘어가서 고생했다. 공부하자. 

2. 이중 리스트를 다루는 것을 연습해야겠다. 

3. for문을 돌릴 때 튜플의 인자를 나눠서 받을 수 있는 것은 기억하자

4. heppush로 리스트를 받으면 sort를 안 해도 된다. 

5. 무한대(inf) 기억 하기