백준 1916 최소비용 구하기 파이썬 풀이, 시간초과, heapq vs deque

난이도 : 골드5

풀이일 : 2401151

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 - 시간초과

import sys
from collections import deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

load = [[] for _ in range(N+1)]
result = []

for i in range(M):
    S, E, M = list(map(int, sys.stdin.readline().split()))
    load[S].append([E, M])

s, e = list(map(int, sys.stdin.readline().split()))

queue = deque()
queue.append(s)
visited = [100001 for _ in range(N + 1)]
visited[s] = 0

while queue:
    now = queue.popleft()
    for i in load[now]:
        if visited[i[0]] > visited[now] + i[1]:
            visited[i[0]] = visited[now] + i[1]
            if i[0] == e:
                result.append(visited[i[0]])
            queue.append(i[0])

print(min(result))

코드 구성

• load : 연결된 도시의 정보와, 요금 정보를 저장
• result : 도착 도시에 갈 수 있는 경우의 총 비용 저장
• visited : 이동 금액을 저장할 배열
  • 100000 이 최대비용이므로 100001로 모든 값을 설정
• while문
  • 시작 도시와 연결되어 있는 도시들을 확인하며, 이동 요금 합산
• result 배열의 최솟값 출력

---

2차 시도 오답 - 시간초과

import sys, heapq

def dijkstra(num):
    visited = [100001 * N for _ in range(N+1)]
    visited[num] = 0
    queue = []
    heapq.heappush(queue, [visited[num], num])

    while queue:
        count, now = heapq.heappop(queue)

        for i in load[now]:
            if visited[i[0]] > count + i[1]:
                heapq.heappush(queue, [count + i[1], i[0]])
                visited[i[0]] = count + i[1]

    return visited


N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

load = [[] for _ in range(N+1)]

for i in range(M):
    S, E, M = list(map(int, sys.stdin.readline().split()))
    load[S].append([E, M])

start, end = list(map(int, sys.stdin.readline().split()))

result = dijkstra(start)

print(result[end])

코드 변화

• 다익스트라 알고리즘을 공부하고, heapq를 사용

---

3차 시도 정답

import sys, heapq

def dijkstra(num):
    visited = [100001 * N for _ in range(N+1)]
    visited[num] = 0
    queue = []
    heapq.heappush(queue, [visited[num], num])

    while queue:
        count, now = heapq.heappop(queue)

        if count <= visited[now]:
            for i in load[now]:
                if visited[i[0]] > count + i[1]:
                    heapq.heappush(queue, [count + i[1], i[0]])
                    visited[i[0]] = count + i[1]

    return visited


N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

load = [[] for _ in range(N+1)]

for i in range(M):
    S, E, M = list(map(int, sys.stdin.readline().split()))
    load[S].append([E, M])

start, end = list(map(int, sys.stdin.readline().split()))

result = dijkstra(start)

print(result[end])

코드 변화

• visited 배열의 숫자 설정이 잘못 된 것을 발견하고 최대 요금 * 도시 수 로 변경
• count 와 visited[now]를 비교하는 조건문 추가

---

4차 시도 정답

import sys
from collections import deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

load = [[] for _ in range(N+1)]
result = []

for i in range(M):
    S, E, M = list(map(int, sys.stdin.readline().split()))
    load[S].append([E, M])

s, e = list(map(int, sys.stdin.readline().split()))

queue = deque()
queue.append([s, 0])
visited = [100001 * N for _ in range(N + 1)]
visited[s] = 0

for i in range(N+1):
    if load[i]:
        load[i].sort(key=lambda x: x[1])

while queue:
    now, count = queue.popleft()
    if count <= visited[now]:
        for i in load[now]:
            if visited[i[0]] > visited[now] + i[1]:
                visited[i[0]] = visited[now] + i[1]
                if i[0] == e:
                    result.append(visited[i[0]])
                queue.append([i[0], count + i[1]])

print(min(result))

heapq를 사용했을 때에도 시간초과가 났던 데에서 출발해 1차 시도를 heapq없이 다시 수정한 버전

 

코드 변화

• load 정렬 추가
  • load[i]가 있는 경우, 요금인 x[1] 번째 요소를 기준으로 정렬 -> 처음엔 조건문을 달지 않았다가 인덱스 에러가 발생했다.
• count 와 visited[now]를 비교하는 조건문 추가
• queue에 도시 정보와 함께 요금 정보도 추가하도록 변경

---

배운것

• heapq : 트리 형태 자료구조, 부모 노드 값이 항상 자식 노드보다 작거나 같은 min heap 형태
• heapq.heappush(heap, a) : heap에 a를 정렬해서 추가
• heapq.peappop : 루트에 위치한 가장 작은 원소 반환 및 제거

---

느낀점

• heapq를 새로 공부하기 싫어서 예전에 정렬을 사용했었는데, 안되는 줄 알고 힙큐를 공부했지만, 결국 로직의 문제였다 공부한게 아깝지는 않지만 충분히 생각해보자. 이참에 공부하게 된 건 좋은 일이지!
• lambda 식을 하도 오랫만에 써서 헤매다가 제대로 썼다. 안쓰는 기능들을 잊지 않도록 반복하고 익숙해지자. 새로운 걸 배우면 비슷한 유형의 문제로 반복하고, 잊기 전에 가끔씩 비슷한거 풀어보기