오늘의 회고

이틀 전 union find 알고리즘을 공부하고 오늘은 관련된 문제인 1717번 집합의 표현을 풀어봤다.

---

시도한 것

풀면서 에러가 다양한 에러가 많이 났다.

Recursion Error

recursion error가 뜬 코드이다.

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

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y


n, m = map(int, input().split())
parent = list(range(n+1))

for _ in range(m):
    s, a, b = map(int, input().split())
    if s == 0:
        union(a, b)
    else: # s==1
        if find(a) == find(b):
            print('YES')
        else:
            print('NO')

그래서 메인 코드에서 s==1일때 find(a) == find(b) 찾는데 에러가 났나 생각해서

for _ in range(m):
    s, a, b = map(int, input().split())
    if s == 0:
        union(a, b)
    else: # s==1
        if parent[a] == parent[b]:
            print('YES')
        else:
            print('NO')

이 부분을 이렇게 고쳤더니 아예 틀렸다고 떴다...
parent에는 루트 값만 넣는데 왜 틀렸다고 나오는지 고민을 좀 해봐야겠다.

해결방법

import sys
sys.setrecursionlimit(1000000) # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

코드 맨 앞에 재귀 깊이 제한을 늘리는 코드를 작성했더니 Recursion Error를 해결했다.

하지만...

메모리 초과가 나왔다

그래서 제출을 pypy3가 아니라 Python3로 했더니 해결!
이 둘의 차이점은 pypy3는 시간 절약, 메모리 많이 차지
python3는 시간은 오래걸리지만 메모리 pypy3보다 덜 차지
그래서 python3로 바꾸었다!

정답 코드

import sys
sys.setrecursionlimit(1000000) # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

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

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y


n, m = map(int, input().split())
parent = list(range(n+1))

for _ in range(m):
    s, a, b = map(int, input().split())
    if s == 0:
        union(a, b)
    else: # s==1
        # if parent[a] == parent[b]:
        if find(a) == find(b):
            print('YES')
        else:
            print('NO')