백준 11779 최소비용 구하기 2 파이썬 풀이

난이도 : 골드3

풀이일 : 2401173

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

11779번: 최소비용 구하기 2

---

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

---

1차 시도 오답

import sys, heapq

def djikstra(num):
    visited[num] = [0, f'{num}']
    queue = []
    heapq.heappush(queue, [visited[num], num])

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

        if load[0] <= visited[now][0]:
            for add, next in bus[now]:
                if visited[next][0] > load[0] + add:
                    visited[next][0] = load[0] + add
                    visited[next][1] = load[1] + f'{next}'
                    heapq.heappush(queue, [visited[next], next])

    return

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
bus = [[] for _ in range(n + 1)]
visited = [[n * 100000, ""] for _ in range(n+1)]

for _ in range(m):
    s, e, v = list(map(int, sys.stdin.readline().split()))
    bus[s].append([v, e])

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

djikstra(start)

print(visited[end][0])
print(len(visited[end][1]))
for i in visited[end][1]:
    print(i, end=" ")

코드 구성

• 다익스트라 풀이
• bus의 출발도시 번호에 도착 도시까지의 비용과 도착 도시의 정보를 리스트로 추가
• visited 배열을 2차원으로 구성하여, 비용과 지나온 도시 정보를 함께 저장하도록 설정
• 다익스트라 방식으로 출발도시부터 도착도시까지의 최소 비용, 지나온 도시를 탐색

틀린 이유

• 문자열로 지나온 도시를 저장해두었기 때문에, 두 자리수 이상의 숫자 도시에서 출력 시 문제 발생
• ex) 10 번 도시를 거쳐왔을 경우, 1과 0 도시를 지나온 것처럼 출력

---

2차 시도 오답 - 시간초과

import sys, heapq

def djikstra(num):
    visited[num] = [0, [num]]
    queue = []
    heapq.heappush(queue, [visited[num], num])

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

        if load[0] <= visited[now][0]:
            for add, next in bus[now]:
                if visited[next][0] > load[0] + add:
                    visited[next][0] = load[0] + add
                    visited[next][1] = load[1] + [next]
                    heapq.heappush(queue, [visited[next], next])
    return

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
bus = [[] for _ in range(n + 1)]
visited = [[int(1e9), []] for _ in range(n+1)]

for _ in range(m):
    s, e, v = list(map(int, sys.stdin.readline().split()))
    bus[s].append([v, e])

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

djikstra(start)

print(visited[end][0])
print(len(visited[end][1]))

for i in visited[end][1]:
    print(i, end=" ")

코드 변화

• visited의 최댓값을 1e9로 변환
• 특정 도시의 visited 내부에서 지나온 도시 저장 방식을 문자열에서 리스트로 변환

틀린 이유

• 다익스트라 내부에서 append 방식을 사용하였기 때문에, 매 번 리스트를 복사하는 과정에서 시간초과 발생

---

3차 시도 정답

import sys, heapq

def djikstra(num):
    visited[num] = 0
    queue = []
    heapq.heappush(queue, [0, num])

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

        if cost <= visited[now]:
            for add, next in bus[now]:
                if visited[next] > cost + add:
                    visited[next] = cost + add
                    previous[next] = now
                    heapq.heappush(queue, [cost + add, next])
    return

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
bus = [[] for _ in range(n + 1)]
visited = [int(1e9) for _ in range(n+1)]
previous = [-1 for _ in range(n + 1)]

for _ in range(m):
    s, e, v = list(map(int, sys.stdin.readline().split()))
    bus[s].append([v, e])

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

djikstra(start)
result = [end]

print(visited[end])

while end != start:
    end = previous[end]
    result.append(end)

print(len(result))

for i in result[::-1]:
    print(i, end=" ")

코드 변화

• visited 배열을 1차원 배열로 수정
• previous 배열을 생성하여 초기값을 -1로 설정
• 새 도시 방문 시, 이전 도시 정보를 previous 배열에 저장
• 출발 도시에서 도착 도시까지의 최소 비용 구한 후, 반복문을 통해 방문 도시 정보를 탐색
• 구한 방문 도시들을 뒤에서부터 출력

---

느낀점

• 어제, 그저게 다익스트라 문제 풀어서 날로 먹으려고 골랐는데 난이도를 보고 고를걸 그랬다.
• 문자열 코드에서 문제를 찾는데에도, 리스트로 수정 후 문제를 찾는 데에도 생각보다 시간을 너무너무 오래썼다.
• 매일 파이썬 문제랑 자바 문제를 하나씩 풀고 싶으니까 조금씩만 더 빨리 풀기 시작해야지