286. 택배배송
1) 어떤 전략(알고리즘)으로 해결?
다익스트라 (최소비용)
2) 코딩 설명
<내 풀이>
- 아래 풀이는 맞긴 한데 부족한 점이 많이 있다.
- (다익스트라 정석이 아님)
from collections import defaultdict
import heapq
import sys
# N개의 헛간 / 소들의 길 M개
n,m = map(int,sys.stdin.readline().split())
mini_hq= []
rel = defaultdict(list) # defaultdict 리스트로 초기화
# 다익스트라는 초기 비용을 무한대로 초기화
visit_answer = [int(1e9) for _ in range(n+1)]
for i in range(m) :
a,b,c = map(int,sys.stdin.readline().split())
heapq.heappush(rel[a] , (c,b)) # 관계 기록
heapq.heappush(rel[b] , (c,a))
# < 초기화 > : 시작은 1번 노드, 이때 비용은 0원 (1번->1번은 0의 비용)
mini_hq.append((0,1)) # 비용 , 노드 로 집어넣어줌
while mini_hq :
# 검사대상이 존재할 동안 돌려준다.
now_cost , now_node = heapq.heappop(mini_hq)
# 가장 비용이 작은 노드부터 검사 => 그래야 비용이 작은 순으로 채워짐
# 한번 방문한 now_node 는 재방문 X => 먼저 방문된 now_node는 비용 가장 작았던 순이므로
# 한번 pop 됐던 now_node는 이미 visit_answer에 반영돼있음
while rel[now_node] :
# 나랑 이어져있는 노드들 검사
tmp_cost, tmp_node = heapq.heappop(rel[now_node]) # 나랑 이어진 애들 중 비용 가장 적은 애부터 검사
# 한번 POP 돼서 now_node 였던 애들의 rel은 존재하지 않음 => while문 안돌아감 => 자연스레 방문처리 효과
visit_answer[tmp_node] = min(visit_answer[tmp_node] , now_cost+tmp_cost)
# 방문 겸 정답 리스트에 기록된 비용 VS 현재노드 거치는 비용 중 더 작은 것 선택
heapq.heappush( mini_hq, (now_cost+tmp_cost , tmp_node))
# 갱신된 값의 노드를 넣어주기
print(visit_answer[n])
위 코드에서 부족한 점
- 시간 복잡도 :
552ms
부족점 1. 나와 이어져있는 노드 검사 시 나와 이어져만 있다면 , 항상 min으로 비교해서 더 작은 수 넣어주고 모두 큐에 넣어줌
1번 보완 : 기록된 비용보다 now_node 거친 비용이 더 적을 시에만 큐에 넣어주기
- 시간 복잡도 :
476ms
while rel[now_node] : # 나랑 이어져있는 노드들 검사 tmp_cost, tmp_node = heapq.heappop(rel[now_node]) # 나랑 이어진 애들 중 비용 가장 적은 애부터 검사 # 한번 POP 돼서 now_node 였던 애들의 rel은 존재하지 않음 => while문 안돌아감 => 자연스레 방문처리 효과 if visit_answer[tmp_node] > now_cost+tmp_cost : # 기존 풀이 : 매번 min으로 비교 후 큐에 넣어주었음 # 변경 풀이 : 기록된 비용보다 now_node 거친 비용이 더 적을 시에만!! visit_answer[tmp_node] = now_cost+tmp_cost heapq.heappush( mini_hq, (now_cost+tmp_cost , tmp_node)) # 갱신된 값의 노드를 넣어주기부족점 2. 나와 이어져있는 노드 검사하고 매번 heapq.pop
2번 보완 : 그저 for문으로 나와 이어져있는 노드 검사하기
- 시간 복잡도 :
384ms
for tmp_cost, tmp_node in rel[now_node] : # 나랑 이어져있는 노드들 검사 # 기존 : 이것도 min heap 으로 pop 해주었음 # 변경 : for 문으로 검사 if visit_answer[tmp_node] > now_cost+tmp_cost : # 방문 겸 정답 리스트에 기록된 비용 VS 현재노드 거치는 비용 중 더 작은 것 선택 visit_answer[tmp_node] = now_cost+tmp_cost heapq.heappush( mini_hq, (now_cost+tmp_cost , tmp_node)) # 갱신된 값의 노드를 넣어주기
보완한 코드
from collections import defaultdict
import heapq
import sys
# N개의 헛간 / 소들의 길 M개
n,m = map(int,sys.stdin.readline().split())
mini_hq= []
rel = defaultdict(list) # defaultdict 리스트로 초기화
# 다익스트라는 초기 비용을 무한대로 초기화
visit_answer = [int(1e9) for _ in range(n+1)]
for i in range(m) :
a,b,c = map(int,sys.stdin.readline().split())
heapq.heappush(rel[a] , (c,b)) # 관계 기록
heapq.heappush(rel[b] , (c,a))
# < 초기화 > : 시작은 1번 노드, 이때 비용은 0원 (1번->1번은 0의 비용)
mini_hq.append((0,1)) # 비용 , 노드 로 집어넣어줌
while mini_hq :
# 검사대상이 존재할 동안 돌려준다.
now_cost , now_node = heapq.heappop(mini_hq)
# 가장 비용이 작은 노드부터 검사 => 그래야 비용이 작은 순으로 채워짐
# 한번 방문한 now_node 는 재방문 X => 먼저 방문된 now_node는 비용 가장 작았던 순이므로
# 한번 pop 됐던 now_node는 이미 visit_answer에 반영돼있음
for tmp_cost, tmp_node in rel[now_node] :
# 나랑 이어져있는 노드들 검사
# 기존 : 이것도 min heap 으로 pop 해주었음
# 변경 : for 문으로 검사
if visit_answer[tmp_node] > now_cost+tmp_cost :
# 방문 겸 정답 리스트에 기록된 비용 VS 현재노드 거치는 비용 중 더 작은 것 선택
# 기존 풀이 : 매번 min으로 비교 후 큐에 넣어주었음
# 변경 풀이 : 기록된 비용보다 now_node 거친 비용이 더 적을 시에만!!
visit_answer[tmp_node] = now_cost+tmp_cost
heapq.heappush( mini_hq, (now_cost+tmp_cost , tmp_node))
# 갱신된 값의 노드를 넣어주기
print(visit_answer[n])
< 내 틀렸던 풀이, 문제점>
(1) 38프로까지 갔다가 틀린 풀이
from collections import defaultdict, deque
import heapq
import sys
# N개의 헛간 / 소들의 길 M개
n,m = map(int,sys.stdin.readline().split())
rel = defaultdict(list)
mini_hq= []
visit_answer = [int(1e9) for _ in range(n+1)]
for i in range(m) :
a,b,c = map(int,sys.stdin.readline().split())
heapq.heappush(rel[a] , (c,b))
heapq.heappush(rel[b] , (c,a))
mini_hq.append((0,1))
visit_answer[1] = 0
while mini_hq :
now_cost , now_node = heapq.heappop(mini_hq)
while rel[now_node] :
tmp_cost, tmp_node = heapq.heappop(rel[now_node])
# 나랑 이어진 애들 중 비용 가장 적은 애부터
if visit_answer[tmp_node] <= now_cost:
continue
else :
visit_answer[tmp_node] = now_cost+tmp_cost
heapq.heappush( mini_hq, (now_cost+tmp_cost , tmp_node))
print(visit_answer[n])
<반성 점>
다익스트라는 초기화 무한대, 우선순위 큐 사용이 핵심 !
<배운 점>
defaultdict 초기화 방법
int_dict = defaultdict(int)
초기값이 int인 0으로 주어진다.
list_dict = defaultdict(list)
초기값이 list 형태로 []가 주어진다.
set_dict = defaultdict(set)
초기값이 set 형태로 {}가 주어진다.
defaultdict 출처 블로그
