영최의 개발켈로그

링크: https://www.acmicpc.net/problem/1261✅ 벽을 부순다 = 벽의 비용을 더했을때 최소비용이된다 => 다익스트라import heapqM,N = map(int,input().split())graph = [list(map(int,list(input()))) for _ in range(N)]INF = int(1e9)distance = [[INF]*M for _ in range(N)]dr = [-1,0,1,0]dc = [0,1,0,-1]def dijkstra(start_r,start_c): distance[start_r][start_c]=0 q=[] heapq.heappush(q,(0,(start_r,start_c))) while q: dist,(..

✅ 특정노드사이의 비용을 최소비용으로 잘못판단했다. => 이부분(start_v1[v2],start_v2[v1]) / 어느 지점을 특히 지나가야한다면 그사이에서도 다른 노드를 지날때가 더 최소일 수도 있다는걸 명심하자#수정 후path_1_v1_v2_N = start_1[v1]+start_v1[v2]+start_v2[N]path_1_v2_v1_N = start_1[v2]+start_v2[v1]+start_v1[N]#수정 전v1_v2_cost=INFfor (node, cost) in graph[v1]: if node==v2: v1_v2_cost=costpath_1_v1_v2_N = start_1[v1]+v1_v2_cost+start_v2[N]path_1_v2_v1_N = start_1[v2]..

✅ 이동시 -1 이 있으므로 최대 max(N,K)*2만큼의 배열이 필요하다 (입력이 5 17 일때 : 5->10->20->17)import heapqINF = int(1e9)N,K = map(int,input().split())distance = [INF]*(max(N,K)*2+1)def dijkstra(start): distance[start]=0 q=[] heapq.heappush(q,(0,start)) while q: dist, now = heapq.heappop(q) if distance[now]next_dist: distance[next_now]=next_dist heapq.heappush(q,(..