글 읽기 - python 메모리초과

ert1015 1년 전 0

최소 스패닝 트리를 이용해서 문제를 시도해봤지만 메모리 초과가 뜹니다.. 조언부탁드립니다.

import sys
input = sys.stdin.readline

def f_parent(x):
    if x != parent[x]:
        parent[x] = f_parent(parent[x])
    return parent[x]

def u_parent(x, y):
    x, y = f_parent(x), f_parent(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

n, c = map(int, input().split())
info = []
data = [list(map(int, input().split())) for _ in range(n)]
parent = [i for i in range(n)]

for i in range(n):
    for j in range(i+1, n):
        tmp = abs((data[i][0]-data[j][0])**2) + abs((data[i][1]-data[j][1])**2)
        if tmp >= c:
            info.append((i, j, tmp))
info.sort(key = lambda x:x[2])
ans, ct = 0, 0
for i in info:
    x,y,z = i
    if f_parent(x) != f_parent(y):
        u_parent(x, y)
        ans += z
        ct += 1
print(ans if ct >= n-1 else -1)

corona1993 1년 전 1

info.sort 대신에 heapq를 사용하니까 메모리 초과 안뜨네요.

저의 코드 제출 이력중에 해당 부분만 변경해서 제출한게 있으니 참고해보세요.

이유는 잘 모르겠습니다.

구글링해서 찾아보고 있는데 쉽지 않네요. (혹시 아시는 분 계시면 댓글 달아주세요)

+ 그리고, 간선 추가할 때마다 c +=1 이 아니라, ct+=1로 변경해주셔야될 것 같네요

ert1015 1년 전 0

ct로 바꾼 코드를 올려야 했는데 잘못올렸네요 heapq이용해서 풀어보겠습니다 감사합니다!

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

문제

문제

출처

ICPC

python 메모리초과

ert1015 1년 전 0

corona1993 1년 전 1

ert1015 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말