1238

날짜 : 2023. 09. 24

사용 언어 : python

 

문제

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

 

 

코드

import sys
import heapq

n, m, x = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    start, end, cost = map(int, sys.stdin.readline().split())
    graph[start].append([end, cost])

INF = int(1e9)
res = list()

def dijkstra(start, end):
    dist = [INF] * (n + 1)  # start 기준으로 거리
    dist[start] = 0  # 본인 제외
    queue = list()
    heapq.heappush(queue, [0, start])
    while queue:
        now_dist, now_node = heapq.heappop(queue)
        # print(now_node, now_dist)
        if now_dist > dist[now_node]: continue  # 기존 거리가 더 짧은 경우
        for i in graph[now_node]:
            d = now_dist + i[1]
            if d < dist[i[0]]:  # 거쳐서 가는 거리가 더 짧은 경우
                dist[i[0]] = d
                heapq.heappush(queue, [d, i[0]])
    return dist[end]


for i in range(1, n+1):
    if i == x: continue  # 이동하지 않는 경우
    # print("node %d"%(i))
    res.append(dijkstra(i, x) + dijkstra(x, i))

print(max(res))

 

 

풀이

- 각 노드에서부터 도착지(x)까지의 거리 + 도착지(x)에서부터 각 노드의까지의 거리를 더한 값 중에서 최대값을 출력하는 문제다.

- 각 노드를 시작점으로 삼고 도착지로 가는 다익스트라를 실행하되 다시 돌아오는 경우도 있기 때문에 루프를 한번 돌 때마다 2번을 실행한다.

- 다만 이동하지 않는 경우도 있기 때문에 해당 케이스는 제외시킨다.

 

 

알게된 점

- 맨 처음 문제를 이해하는데 시간이 걸렸고, 다익스트라를 구현함에 있어 또 시간이 걸렸다.

- heapq를 사용하면서 그래프를 (n+1) x (n+1)로 하는 바람에 구현 과정에서 어려움이 있었기 때문에 빈 리스트를 만들고 입력 시 (cost, 노드) 형태로 삽입하는 방식으로 구현했다.

- 그리고 우선순위 큐를 돌리는 과정에서 heapq 정렬방식을 확실하게 몰랐기 때문에 heapq.heappush(queue, [노드번호, cost])로 되어 무한루프가 발생하기도 했었다.

- 일차적으로 다익스트라 구현을 확실하게 하지 못하는 점이 이 문제를 풀면서 가장 어렵게 나타난 것 같았다.

- 그리고 시간으로는 3204ms가 나왔는데 아마 heap을 사용하지 않았다면 분면 TLE가 발생했을 듯 하다

 

 

참고 사이트

-