글 읽기 - 파이썬 크루스칼로 풀 수 있는건가요?

alstn113 2년 전 0

아무리 고쳐도

python으로 하면 recursion에러 뜨고

pypy로 하면 메모리초과가 뜨네요

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)


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


def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


v, e = map(int, input().split())
s_p, e_p = map(int, input().split())
parent = [i for i in range(v+1)]
edges = []

for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))


edges.sort(reverse=True)


def answer():
    result = 1e9
    for edge in edges:
        cost, a, b = edge
        if find_parent(a) != find_parent(b):
            union_parent(a, b)
            result = min(cost, result)
        if parent[s_p] == parent[e_p]:
            print(result)
            return
    print(0)


answer()

seungwuk98 2년 전 0

가능하네요. 방금 AC 받았습니다.

랭크를 사용해서 재귀 깊이를 줄여야합니다. 256MB로 아슬아슬하게 통과했네요.

seungwuk98 2년 전 0

pypy3로 했습니다.

seungwuk98 2년 전 0

그리고 재귀 깊이는 10000보다는 당연히 커야합니다.

alstn113 2년 전 0

혹시 랭크가 뭔지 알 수 있을까요?

파이썬 랭크 재귀로 검색해도 잘 나오지를 않네요

seungwuk98 2년 전 0

랭크는 크루스칼 알고리즘에만 있는 개념입니다.

랭크 배열을 놓고 랭크가 높은 것이 부모가 되고, 같으면 둘중 하나를 부모로 놓고, 랭크를 하나씩 더해줍니다.

이렇게 하면 재귀 깊이를 절반 이하로 줄일 수 있습니다.

seungwuk98 2년 전 0

테스트해보니까 추가 재귀 깊이를 설정 안해도 통과하는 것 같네요. 파이썬은 재귀 깊이만 깊게 설정해도 메모리를 많이 잡아먹습니다.

alstn113 2년 전 0

감사합니다. 다양하게 테스트하면서 지식이 늘었습니다

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