글 읽기 - (Python3) 다익스트라로 접근, 시간초과

dojun2006 3년 전 1

트리도 일단 그래프의 일종이므로 다익스트라로 접근할 수 있을 것 같다고 생각했습니다.

거리가 최대 10,000이여서 무한대 대신 16,384라는 정수를 사용했습니다.

파이썬 heapq 모듈의 문제인지 찾아봤으나 이것도 충분히 빠르게 동작하는 것 같습니다.

그렇다면 제 로직의 문제일텐데, 뭐가 문제인지 잘 모르겠네요...

다익스트라 로직에서 목적지에 해당하는 노드가 나오면 바로 루프를 끝내도록 한 부분을 수정했는데 이게 문제일까요?

다들 bfs, dfs로 푸시던 것 같던데, 다익스트라가 아니라 bfs나 dfs로 접근해야만 할까요?

import sys
import heapq

n, m = map(int, input().split())
dist = [[16384] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dist[i][i] = 0

for _ in range(n - 1):
    p1, p2, d = map(int, sys.stdin.readline().split())
    dist[p1][p2] = d
    dist[p2][p1] = d

for _ in range(m):
    src, dest = map(int, sys.stdin.readline().split())
    src_dist = []

    for i in range(1, n + 1):
        if i != src:
            heapq.heappush(src_dist, [dist[src][i], i])
    
    # heap에 들어간 data 수가 최대 n-1개 이므로 n-1번만 반복
    for i in range(n - 1):
        node = heapq.heappop(src_dist)
        # node[1]이 노드 번호, node[0]은 그 노드까지 거리
        w = node[1]
        # 보통의 다익스트라 로직과 다른 부분; 목적지에 해당하는 노드 나오면 바로 끝냄
        if w == dest:
            print(node[0])
            break

        for vertex in src_dist:
            vertex[0] = min(vertex[0], node[0] + dist[w][vertex[1]])
        heapq.heapify(src_dist)

growing 2년 전 1

1. 거리가 10000이하 라고 하여도, 거리를 더하다 보면 16384 보다 커질 수 있습니다.

2. 음수인 거리가 나올수도 있지만 다익스트라로 푸셔도 무방한 이유는 완벽한 트리 구조이기 때문입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(Python3) 다익스트라로 접근, 시간초과

dojun2006 3년 전 1

growing 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말