백준 1238) 파티_Python

# 문제

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

1238번: 파티

#문제 분석

- 처음에는 플로이드-워셜로 충분히 풀 수 있는 문제라고 생각했다. 각 노드로 가는 최단 거리들을 구한 다음에, i->X로 가는 최단 거리+   X->i로 가는 최단 거리를 더해줘서 이의 최대값을 구하는 식으로 문제를 풀었다.

import sys

input=sys.stdin.readline
N,M,X=map(int,input().split())
board=[[float('inf')]*(N) for _ in range(N)]

for _ in range(M):
    A,B,T=map(int,input().split())
    board[A-1][B-1]=T

for mid in range(N):
    for i in range(N):
        for j in range(N):
            if i==j:
                board[i][j]=0
            else:
                board[i][j]=min(board[i][j],board[i][mid]+board[mid][j])


#시작에서 X
answer=0
for i in range(N):
    answer=max(answer,board[i][X]+board[X][i])
print(answer)

- 그러나 이 문제는 노드의 입력값이 1000이다. 따라서 n(V^3)이 되는 플로이드 워셜의 시간복잡도로는 파이썬으로 컴파일했을 때 1초가 넘어갈 위험성이 크다. 실제로도 시간 초과가 계속 발생하는 코드이다. 따라서 해당 문제를 다익스트라로 전환해서 풀었다.

- 근데 왜 골3인지는 잘 모를..

#코드

from collections import defaultdict
import sys
import heapq

INF=sys.maxsize

def dijkstra(start,end):

    heap=[]
    heapq.heappush(heap,[0,start])
    dist=[INF]*(N+1)
    dist[start]=0

    while heap:
        cur_dist,cur=heapq.heappop(heap)

        for nxt,nxt_dist in graph[cur]:
            accumulate_dist=cur_dist+nxt_dist

            if accumulate_dist<dist[nxt]:
                dist[nxt]=accumulate_dist
                heapq.heappush(heap,[accumulate_dist,nxt])
        
    #start~end까지의 최단거리를 리턴해준다.
    return dist[end]


input=sys.stdin.readline
N,M,X=map(int,input().split())
graph=defaultdict(list)

for _ in range(M):
    A,B,T=map(int,input().split())
    graph[A].append((B,T))

answer=[]
for i in range(1,N+1):
    if i!=X:
        #각 노드들에서 i~X까지의 최단 거리 + X~i로 돌아오는 최단 거리의 최댓값을 구해준다.
        answer.append(dijkstra(i,X)+dijkstra(X,i))

print(max(answer))

 

+) 멍청하게 우선순위 큐를 거리대로 정렬해야 했는데.. 반대로 노드를 앞에두고 힙 정렬 했으면서 한 시간 동안 맞왜틀 시전하고 있었다; 작은 디테일로 시간을 낭비할 수 있으니 코드를 꼼꼼히 짜자..

- 틀린 코드 

def dijkstra(start,end):

    heap=[]
    heapq.heappush(heap,[start,0])
    dist=[INF]*(N+1)
    dist[start]=0

    while heap:
        cur,cur_dist=heapq.heappop(heap)

        for nxt,nxt_dist in graph[cur]:
            accumulate_dist=cur_dist+nxt_dist

            if accumulate_dist<dist[nxt]:
                dist[nxt]=accumulate_dist
                heapq.heappush(heap,[nxt,accumulate_dist])
        
    #start~end까지의 최단거리를 리턴해준다.
    return dist[end]