글 읽기 - 시간초과 왜 나는걸까요 ㅠㅠ

ekfrhkquf12 1년 전 0

union-find로 구현했습니다.

교과서 읽고 collapsing find와 weighted union를 적용해보려 했는데 제가 어딘가에서 구현을 어색하게 했는지 1%에서 시간초과가 나네요. 어디가 잘못된건지 잘 모르겠는데 좀 도와주실 분 계실까요 ㅠㅠ

#https://www.acmicpc.net/problem/1647
#union-find 연습문제
def find(node, parent):
    i = node
    while True:
        if parent[i-1] == -1:
            break
        # collapse
        parent[node-1] = parent[i-1]
        i = parent[i-1]

    return i


def union(this_node, that_node, parent):
    this_parent = find(this_node, parent)
    that_parent = find(that_node, parent)
    #weighted union 해야함
    this_count = parent.count(this_parent)
    that_count = parent.count(that_parent)

    if this_count > that_count:
        parent[find(that_node, parent)-1] = find(this_node, parent)
    else:
        parent[find(this_node, parent)-1] = find(that_node, parent)


import sys
from queue import PriorityQueue
(N, M) = list(map(int, sys.stdin.readline().split()))
my_queue = PriorityQueue()
for _ in range(M):
    (origin, destination, cost) = list(map(int, sys.stdin.readline().split()))
    my_queue.put([cost, origin, destination])

#parent 노드 설정해주기
parent = []
for _ in range(N):
    parent.append(-1)

connected = False
total_cost = 0
while my_queue and not connected:
    [cost, origin, destination] = my_queue.get()
   # print([cost, origin, destination])
    origin_parent = find(origin, parent)
    destination_parent = find(destination, parent)
    last = 0
    if origin_parent != destination_parent:
        union(origin, destination, parent)
        total_cost += cost
        last = cost
    if origin_parent == -1 and destination_parent == -1:
        union(origin, destination, parent)
        total_cost += cost
        last = cost
    if parent.count(-1) == 1:
        connected = True

print(total_cost-last)
#print(parent)

ekfrhkquf12 1년 전 0

chat gpt한테 물어봐서 코드 조금 수정하고 제출했더니 통과했습니다

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

문제

문제

출처

ICPC

시간초과 왜 나는걸까요 ㅠㅠ

ekfrhkquf12 1년 전 0

ekfrhkquf12 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말