글 읽기 - 1647번 파이썬으로 크스칼 알고리즘 구현했는데 시간 초과가 납니다.

drather 4년 전 0

데이터 입력받는게 걸리는 시간을 줄이기 위해 sys.stdin.readline()을 사용했습니다

간선을 오름차순으로 정렬하기 위해 heap 사용하였구요.

그런데도 시간 초과가 나는 걸 보니, 반례가 있는 것 같습니다.

열심히 들여다도 보고, 구글링도 해봤지만 결국 답을 못찾아서 질문 올립니다.

부디 가엾게 여기시고 도와주시기 바랍니다.

import heapq as hq
import sys
node_num, link_num = map(int, input().split())
node_num += 1

edges = []
for i in range(link_num):
    start, dest, weight = map(int, sys.stdin.readline().split())
    hq.heappush(edges, [weight, start, dest])

rank = {}
parent = {}

# rank와 parent 초기화
def make_set(node):
    parent[node] = node
    rank[node] = 0

# 최상위 노드 찾기
def find_set(node):
    if parent[node] != node:
        parent[node] = find_set(parent[node])

    return parent[node]

# 두 집합 합치기
def union_set(node1, node2):
    root1 = find_set(node1)
    root2 = find_set(node2)

    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2

            if rank[root1] == rank[root2]:
                rank[root2] += 1

# 크루스칼 알고리즘
def kruskal(node_num, edges):
    for i in range(node_num):
        make_set(i)

    mst = []
    answer = 0

    while len(mst) < node_num and edges:
        edge = hq.heappop(edges)
        weight, start, dest = edge

        if find_set(start) != find_set(dest):
            union_set(start, dest)
            mst.append(edge)
            answer += edge[0]

    answer -= mst[-1][0]

    print(answer)


kruskal(node_num, edges)

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

문제

문제

출처

ICPC

1647번 파이썬으로 크스칼 알고리즘 구현했는데 시간 초과가 납니다.

drather 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말