[백준] 1717번 집합의 표현(python)

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

1. 난이도 골드5 (🥇)

 

2. 문제 해결 방법

union find 알고리즘을 이용해서 문제를 해결하면 된다. n과 m의 값이 크기 때문에 경로압축을 통해 시간복잡도를 감소시켰다.

 

잘 푼 것 같은데 자꾸 런타임 에러가 발생해서 왜일까 한참 고민했는데 setrecursionlimt를 설정해주지 않았었고, 이를 수정했더니 잘 출력되었다.

 

10만으로 설정하면 잘 통과되지만 100만으로 설정했을땐 메모리초과가 발생한다. 아직 union find 이해도가 높지 않아서 정확하겐 모루겠다 다음에 다시 수정하러 오겠슴,,

 

3. 내가 작성한 코드

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

def find(x): #루트 노드가 parent에 들어감
  if parent[x] != x:
    parent[x] = find(parent[x])
  return parent[x]

def union(a,b):
  a = find(a)
  b = find(b)

  if a < b:
    parent[b] = a
  else:
    parent[a] = b

n,m = map(int, input().rstrip().split()) #n집합개수 m연산개수
parent = [0] * (n+1)

for i in range(n+1):
  parent[i] = i

for _ in range(m):
  op,a,b = map(int, input().rstrip().split())

  if op == 0:
    union(a,b)
  
  else:
    a = find(a)
    b = find(b)

    if a != b:
      print("NO")
    else:
      print("YES")

 

 

재귀를 사용할 때 setrecursionlimit를 통해 재귀 깊이 제한을 갱신해주는 걸 잊지 말자