300. 큰 수 A+B

1) 어떤 전략(알고리즘)으로 해결?

• 다익스트라

2) 코딩 설명

주어진 두 정점은 반드시 통과하며 1번 정점에서 N번 정점으로 최단 거리

후보는 두가지가 있다.
최단 거리 후보 1번 - v1 - v2 - N
최단 거리 후보 2번 - v2 - v1 - N
=>1번, 2번 중 더 최단거리 출력

# 1번 - v1 - v2 - N 
cand1 = dikstra(1,v1 ) + dikstra(v1,v2 ) + dikstra(v2,N )
# 2번 - v2 - v1 - N
cand2 = dikstra(1,v2 ) + dikstra(v2,v1 ) + dikstra(v1,N )
# 갈 수 없는 경우
if cand1>=int(1e9) and cand2>=int(1e9):
    print(-1)
else : 
    print(min(cand1 ,cand2))

<내 풀이>

from collections import defaultdict 
import heapq
import sys

N,E = map(int,sys.stdin.readline().rstrip().split())
road = defaultdict(list)

for _ in range(E) :
    a,b,c = map(int,sys.stdin.readline().rstrip().split())
    road[a].append((b,c))
    road[b].append((a,c))

v1, v2 = map(int,sys.stdin.readline().rstrip().split())

# 주어진 두 정점은 반드시 통과하며 1번 정점에서 N번 정점으로 최단 거리
# 1번 - v1 - v2 - N 
# 2번 - v2 - v1 - N
# 1번, 2번 중 더 최단거리 출력

# a에서 b로 가는 최단거리를 반환값으로 돌려주는 다익스트라 알고리즘 
def dikstra(a,b ) : 
    if a==b : # 출발지와 도착지가 같은 경우 우선 처리 
        return 0
    hq = []
    min_cost = [int(1e9) for _ in range(N+1)]
    min_cost[0] = 0 # 나에게서 나로 가는 비용은 0으로 처리  
    heapq.heappush(hq,(a,0)) # 시작 정점 / 시작 비용
    
    while hq : 
        now_node, now_cost = heapq.heappop(hq)
        if now_cost > min_cost[now_node] :
            continue                                                                                                                                  

        for next_node, next_cost in road[now_node] : 
            if min_cost[next_node] < now_cost + next_cost :
                continue
            else : 
                min_cost[next_node] = now_cost + next_cost
                heapq.heappush(hq,(next_node, now_cost + next_cost))
                
    return(min_cost[b])

# 1번 - v1 - v2 - N 
cand1 = dikstra(1,v1 ) + dikstra(v1,v2 ) + dikstra(v2,N )
# 2번 - v2 - v1 - N
cand2 = dikstra(1,v2 ) + dikstra(v2,v1 ) + dikstra(v1,N )
# 갈 수 없는 경우
if cand1>=int(1e9) and cand2>=int(1e9):
    print(-1)
else : 
    print(min(cand1 ,cand2))
    

< 내 틀렸던 풀이, 문제점>

• 3프로에서 틀리는 풀이

from collections import defaultdict 
import heapq
import sys

N,E = map(int,sys.stdin.readline().rstrip().split())
road = defaultdict(list)

for _ in range(E) :
    a,b,c = map(int,sys.stdin.readline().rstrip().split())
    road[a].append((b,c))
    road[b].append((a,c))

v1, v2 = map(int,sys.stdin.readline().rstrip().split())

# 주어진 두 정점은 반드시 통과하며 1번 정점에서 N번 정점으로 최단 거리
# 1번 - v1 - v2 - N 
# 1번 - v2 - v1 - N

def dikstra(a,b,min_cost) : 
    hq = []
    # 시작 정점 / 시작 비용 
    heapq.heappush(hq,(a,0))
    while hq : 
        now_node, now_cost = heapq.heappop(hq)
        if now_cost > min_cost[now_node] :
            continue                                                                                                                                  

        for next_node, next_cost in road[now_node] : 
            if min_cost[next_node] < now_cost + next_cost :
                continue
            else : 
                min_cost[next_node] = now_cost + next_cost
                heapq.heappush(hq,(next_node, now_cost + next_cost))
                
    return(min_cost[b])

cand1_answer = [ int(1e9) for _ in range(N+1)]
cand1_answer[1] = 0
cand1 = dikstra(1,v1, cand1_answer) + dikstra(v1,v2, cand1_answer) + dikstra(v2,N, cand1_answer)

cand2_answer = [ int(1e9) for _ in range(N+1)]
cand2_answer[1] = 0
cand2 = dikstra(1,v2,cand2_answer) + dikstra(v2,v1,cand2_answer) + dikstra(v1,N,cand2_answer)

if cand1_answer[N]>=int(1e9) and cand2_answer>=int(1e9):
    print(-1)
else : 
    print(min(cand1 ,cand2))

82 프로에서 틀린 풀이

원인 : a에서 b로 가는 최단경로를 출력하는 dikstra(a,b) 에서 a와 b가 같은 경우(출발지와 도착지가 같은 경우) 에 대해서는 최단 거리가 0임을 알려주는 과정을 누락했습니다.

from collections import defaultdict 
import heapq
import sys

N,E = map(int,sys.stdin.readline().rstrip().split())
road = defaultdict(list)

for _ in range(E) :
    a,b,c = map(int,sys.stdin.readline().rstrip().split())
    road[a].append((b,c))
    road[b].append((a,c))

v1, v2 = map(int,sys.stdin.readline().rstrip().split())

# 주어진 두 정점은 반드시 통과하며 1번 정점에서 N번 정점으로 최단 거리
# 1번 - v1 - v2 - N 
# 1번 - v2 - v1 - N

def dikstra(a,b ) : 
    hq = []
    min_cost = [int(1e9) for _ in range(N+1)]
    min_cost[0] = 0
    # 시작 정점 / 시작 비용 
    heapq.heappush(hq,(a,0))
    while hq : 
        now_node, now_cost = heapq.heappop(hq)
        if now_cost > min_cost[now_node] :
            continue                                                                                                                                  

        for next_node, next_cost in road[now_node] : 
            if min_cost[next_node] < now_cost + next_cost :
                continue
            else : 
                min_cost[next_node] = now_cost + next_cost
                heapq.heappush(hq,(next_node, now_cost + next_cost))
                
    return(min_cost[b])

cand1 = dikstra(1,v1 ) + dikstra(v1,v2 ) + dikstra(v2,N )

cand2 = dikstra(1,v2 ) + dikstra(v2,v1 ) + dikstra(v1,N )

if cand1>=int(1e9) and cand2>=int(1e9):
    print(-1)
else : 
    print(min(cand1 ,cand2))

<반성 점>

<배운 점>