[BAEKJOON]백준 11779번 최소 비용 구하기 2 - BFS 탐색 알고리즘, deque 자료구조, defaultdict 해시맵(hashmap)

백준 11779번 최소 비용 구하기 2

백준 11779번 최소 비용 구하기 2

경로와 비용을 defaultdict로 따로 만들어줬다. 두번째 코드는 왜 틀리는지 모르겠다..ㅠㅠ

코드

import sys
import collections
import heapq
import copy
from typing import List, Tuple
input = sys.stdin.readline


class Solution:
    def min_cost(self, start: int, end: int, g: List[List[Tuple]]):
        Q = []
        heapq.heappush(Q, (0, start))

        # 경로 저장
        path = collections.defaultdict(list)

        # 비용
        dist = [sys.maxsize]*1001
        dist[start] = 0

        while Q:
            w, u = heapq.heappop(Q)

            # 드는 비용이 저장된 비용보다 더 큰 경우 continue로 넘긴다.
            if dist[u] < w:
                continue

            # 현재 위치를 현재 path에 저장
            path[u].append(u)

            # 현재 위치가 끝이면
            if u == end:
                return (w, path[u])

            # 현재 위치에서 갈 수 있는곳 반복
            for v, weight in g[u]:

                """갈 수 있는곳까지 갈 때 비용 + 현재까지 총 비용 이렇게 더해서
                dist에 저장된 비용과 비교해서 더 작으면 if 안으로 들어감"""
                if dist[v] > weight + w:

                    # dist 기존에 저장된 값보다 weight + w가 작으니깐 업데이트
                    dist[v] = weight + w

                    # heap에 갈수 있는 위치까지 갈 때 총비용, 갈 수 있는 위치 저장
                    heapq.heappush(Q, (dist[v], v))

                    # 현재 위치까지의 path를 갈수 있는 곳의 path에 복사
                    path[v] = copy.deepcopy(path[u])


n = int(input())
m = int(input())
g = collections.defaultdict(list)
for _ in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))
start, end = map(int, input().split())
answers = Solution().min_cost(start, end, g)
print(answers[0])
print(len(answers[1]))
print(*answers[1])

import sys
input = sys.stdin.readline
import collections
from typing import List, Tuple
import heapq


class Solution:
    def min_cost(self, start: int, end: int, g: List[List[Tuple]]):
        Q = []
        for v, w in g[start]:
            heapq.heappush(Q, (w, str(start)+str(v)))
        visited = [False]*100001
        while Q:
            w, u = heapq.heappop(Q)
            if u[-1] == str(end):
                print(w)
                print(len(set(u)))
                print(*list(u))
                return
            if not visited[int(u[-1])]:
                visited[int(u[-1])] = True
                for v, weight in g[int(u[-1])]:
                    if not visited[v]:
                        heapq.heappush(Q, (w+weight, u+str(v)))


n = int(input())
m = int(input())
g = collections.defaultdict(list)
for _ in range(m):
    u, v, w = map(int, input().split())
    if u != v:
        g[u].append((v, w))
start, end = map(int, input().split())
if start == end:
    print(0)
    print(1)
    print(start)
    exit(0)
Solution().min_cost(start, end, g)