doubleyyh   2년 전

안녕하세요. 파이썬 어린이입니다. 시간 초과가 뜹니다. 어디에서 줄일 수 있을까요? 더해서 제가 파이썬 초보라서 코드 피드백도 해주시면 감사하겠습니다.

N, M = map(int, input().split())


def dijkstra(l, s, e, N):
    check = dict()
    check[s] = True
    distances = dict(l[s])
    while True:
        if check.get(e) is not None:
            break
        maxVal = -float("inf")
        maxIdx = 0
        for i in distances.keys():
            if maxVal < distances[i] and check.get(i) is None:
                maxIdx = i
                maxVal = distances[i]
        if maxIdx == 0:
            break
        check.update({maxIdx: True})

        for c, c2 in l[maxIdx].items():
            if check.get(c):
                continue
            if distances.get(c) is not None and distances[maxIdx] < distances[c]:
                continue
            else:
                t = distances[maxIdx]
                if t > c2:
                    t = c2
                if distances.get(c) is None:
                    distances[c] = t
                elif distances[c] < t:
                    distances[c] = t

    return distances


l = {}
for i in range(N + 1):
    l.update({i: {}})

for i in range(M):
    A, B, C = map(int, input().split())
    if l[A].get(B) is not None and l[A].get(B) < C:
        l[A] = {B: C}
        l[B] = {A: C}
    else:
        l[A].update({B: C})
        l[B].update({A: C})

s, e = map(int, input().split())

check = [False for i in range(N + 1)]
check[s] = True

dist = dict()
dist = dijkstra(l, s, e, N)
if dist.get(e) is None:
    print(0)
else:
    print(dist[e])

wider93   2년 전

시간 초과가 나는 것은 13번 루프가 말해주듯 우선순위를 모든 점을 보면서 구하고 있기 때문입니다. 힙 자료구조를 사용해 보세요.

덤으로, dict에 원소가 들어있는지 없는지에 따라 생기는 귀찮은 분기를 줄이기 위해 collections 모듈의 defaultdict를 이용하면 편합니다. 

doubleyyh   2년 전

wider93

답변 감사합니다. 근데 계속 힙 안에 값들이 변경됩니다. 그런경우에 힙 자료구조가 불가능하지 않나요? 방법이 있으면 알려주시면 감사하겠습니다. 

wider93   2년 전

y까지의 거리가 a에서 b로 변경될 때, 힙에서 (a,y)를 찾을 필요 없이 그냥 (b, y)를 넣어주기만 하면 됩니다. 갱신되는 거리는 항상 작아지기 때문에 힙에서 (b, y)를 먼저 꺼내게 되고, 나중에 나오는 (a,y)는 그냥 무시하면 됩니다.

doubleyyh   2년 전

정말 감사합니다!

doubleyyh   2년 전

힙 자료구조를 이용했는데도 시간 초과가 뜨네요 어디서 줄일 수가 있을까요?

import heapq

N, M = map(int, input().split())


def dijkstra(l, s, e, N):
    heap = []
    check = dict()

    distances = {_: float("inf") for _ in range(N + 1)}
    for i in range(1, N+1):
        if i in l[s]:
            if l[s][i] != 0:
                distances[i] = l[s][i]

    heapq.heappush(heap, (-distances[s], s))
    while heap:
        if check.get(e) is not None:
            break
        maxVal, maxIdx = heapq.heappop(heap)
        if maxIdx in check:
            if check[maxIdx]:
                continue
        else:
            check[maxIdx] = True

        for c, c2 in l[maxIdx].items():
            if check.get(c):
                continue
            if distances[maxIdx] < distances[c] != float("inf") and distances[maxIdx] != float("inf"):
                continue
            else:
                t = distances[maxIdx]
                if t > c2:
                    t = c2
                if distances[c] == float("inf"):
                    distances[c] = t

                elif distances[c] < t:
                    distances[c] = t
                heapq.heappush(heap, (-distances[c], c))

    return distances


l = {}
for i in range(N + 1):
    l.update({i: {}})

for i in range(M):
    A, B, C = map(int, input().split())
    if l[A].get(B) is not None and l[A].get(B) < C:
        l[A] = {B: C}
        l[B] = {A: C}
    else:
        l[A].update({B: C})
        l[B].update({A: C})

s, e = map(int, input().split())

check = [False for i in range(N + 1)]
check[s] = True

dist = dict()
dist = dijkstra(l, s, e, N)
if dist.get(e) is None:
    print(0)
else:
    print(dist[e])

wider93   2년 전

시간 초과는 단순히 빠른 입출력을 사용하지 않아서 나고 있네요. sys.stdin.readline으로 바꾸니 통과합니다.

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