백준/ Gold 1 문제 , 백준 파이썬 2398 , 3인통화 [다익스트라 알고리즘]

백준/ Gold 1 문제 , 백준 파이썬 2398 , 3인통화 [다익스트라 알고리즘]

 

 

풀이 시간

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
잘 풀었다 생각했는데 16%에서 계속 틀림.
다른 블로그 풀이 참고해서 풀었음.

 

 

문제 출처

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

2398번: 3인통화

 

 

풀이

 

 

내가 풀었던 코드이다.

 

dijkstra 함수와 returnRoad 함수는 잘 기능 하였는데

 

밑에 로직을 잘못짠거 같다.

 

나는 A->B, A->C , B->C 로 가는 경우들을 각각 다 구해주었고

 

각 최단 거리의 간선들을 result 배열에 다 담아준다음 new_arr 배열에 중복된거 없이 새로 저장해주었다.

 

이후 세 노드들을 잇는 간선들의 합을 구하기 위해 for 문을 돌려 cnt 변수에 저장해주었고, 이 값과 new_arr에 담긴값들을 맞게 출력해 주었었다.

 

예제는 잘 출력되었지만 제출하면 계속 틀려서 무엇이 잘못되었는지 잘 파악을 못하였음.

 

아마 중복되는 값이 잘 제거되지 못하는 문제가 생긴 것 같다.

 

 

 

 

 

https://velog.io/@dmson1218/%EB%B0%B1%EC%A4%80-2398%EB%B2%88-3%EC%9D%B8%ED%86%B5%ED%99%94

백준 2398번: 3인통화

 

이후 위 블로그를 참고하여  A->B, A->C , B->C 로 가는 방법이 아닌

 

A,B,C 에서 각각 출발하는 다익스트라를 돌려주었고

 

dist를 리턴 받아 각 출발점에서의 거리 합이 가장 작은 인덱스를 point에 저장해 주었다.

 

거리 합이 가장 작은 곳이 바로 이 세 지점들이 연결되는 최단거리이다.

 

이 점을 생각못했었다.

 

이후 이 인덱스부터 각 출발지점까지 되돌아 가는 간선들을 new_arr 라는 리스트에 새로 담아주었고 이 값을 조건에 맞게 출력해주었다.

 

 

 

 

 

 

 

정답

 

from cmath import inf
import heapq
import sys
input=sys.stdin.readline

def dijkstra(start):
    q=[(0,start,0)]
    dist=[inf]*(N+1)
    dist[start]=0
    arr=[0]*(N+1)
    while q:
        Z,X,Y=heapq.heappop(q)
        if dist[X]<Z:
            continue
        for cost,next,now in graph[X]:
            cost+=Z
            if cost<dist[next]:
                dist[next]=cost
                arr[next]=now
                heapq.heappush(q,[cost,next,now])
    return [dist,arr]

def returnRoad(start,end,arr):
    tmp=[]
    while start!=end:
        tmp.append([arr[end],end])
        end=arr[end]
    return tmp

N,M=map(int,input().split())
graph=[[] for _ in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    graph[a].append((c,b,a))
    graph[b].append((c,a,b))
A,B,C=map(int,input().split())

DA=dijkstra(A)
DB=dijkstra(B)
DC=dijkstra(C)
cnt=0
leng=inf
point=0
for i in range(1,N+1):
    if DA[0][i]+DB[0][i]+DC[0][i]<leng:
        point=i
        leng=DA[0][i]+DB[0][i]+DC[0][i] 
         
new_arr=list()
new_arr+=(returnRoad(A,point,DA[1]))        
new_arr+=(returnRoad(B,point,DB[1]))   
new_arr+=(returnRoad(C,point,DC[1]))  

print(leng,len(new_arr))
for i,j in new_arr:
    print(i,j)