백준 1717 집합의 표현 파이썬 풀이

난이도 : 골드5

풀이일 : 2401147

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

1717번: 집합의 표현

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys

N, M = list(map(int, sys.stdin.readline().split()))
parent = [i for i in range(N+1)]

# 부모 노드 찾기
def find(n):
    if parent[n] == n:
        return n
    else:
        return find(parent[n])

# 부모가 다를때 집합 합치기
def add(x, y):
    if find(x) > find(y):
        parent[find(y)] = find(x)
    else:
        parent[find(x)] = find(y)
    return

for i in range(M):
    r, a, b = list(map(int, sys.stdin.readline().split()))
    if r:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")
    else:
        add(a, b)

 

• find : 부모노드를 찾기 위한 함수
  • 부모 노드가 본인이라면 그대로 반환
  • 부모 노드가 본인이 아니라면 부모노드를 넣어 find 함수 재귀호출
• add : 두 집합을 합치기 위한 함수
  • find 함수로 부모 노드를 찾기
  • 부모노드의 숫자가 작은 쪽이 병합 집합의 부모노드가 되도록 설정
• parent : 각 요소의 부모 노드 기록
• r : 현재 요구사항이 두 요소가 포함된 집합을 합치는 것인지, 같은 집합에 있는지 검사하는 것인지 구분
  • 현재 요구사항이 두 요소가 같은 집합에 있는 지 검사하는 것이라면, find 함수를 통해 비교 후 출력
  • 현재 요구사항이 두 요소가 포함된 집합을 합치는 것이라면, add 함수를 통해 두 집합 병합

---

느낀점

• 정말 오랜만에 파이썬으로 알고리즘을 풀어보았다. 인풋 받는 것도 헷갈려서 프린트 찍어가며 풀이했는데, 매일은 아니더라도 익숙해질 만큼은 자주 풀어야지.
• find 함수에서 else문 return을 달지 않는 기초적인 실수로 뭐가 문젠지 들여다봐야했다. 역시 꾸준하게 풀기를 다짐해야지...