[백준] 1717번 집합의 표현 Python 해설

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

1717번: 집합의 표현

Disjoint-set 알고리즘으로 분류된 문제이다.

N사에 떨어졌다고 생각하고 K사 채용연계형 인턴 정형의 코딩 테스트를 봤는데 Disjoint-set문제를 간파하지 못해서 화가 났다. 그래서 끝나자마자 이 문제를 풀었다.

해설은 조금 늦게 작성했다.

 

풀이

---

- Python 정답 코드

import sys
input = sys.stdin.readline

class DisjointSet():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = n

    def find(self, idx):
        while idx != self.parent[idx]: idx = self.parent[idx]
        return idx

    def union(self, a, b):
        #a, b를 입력 받았을 때 a를 기준으로 합한다!
        a = self.find(a)
        b = self.find(b)
        if a == b: return

        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
            self.rank[b] += 1
        else:
            self.parent[b] = a
            self.rank[a] += 1


n, m = map(int, input().split())
obj = DisjointSet(n + 1)
for _ in range(m):
    f, a, b = map(int, input().split())
    if f:
        #a와 b가 같은 집합인지 확인.
        print("YES" if obj.find(a) == obj.find(b) else "NO")
    else:
        #a와 b를 합
        obj.union(a, b)

변수 'f'가 1이면 a, b가 같은 집합인지 확인하고 결과를 출력하게되고, 0이면 a와 b를 합친다.

이 문제해서 "합친다"의 의미는 같은 덩어리라고 봐도 된다.

 

이번 풀이에서는 클래스를 정의해서 풀어봤다.

나는 객체지향 프로그래밍에 너무 경험이 없었기 때문에 이런 문제에서라도 간접적으로 경험을 쌓아보려고 했다.

 

DisjointSet 클래스의 인스턴스를 생성한다.

문제의 입력 n이 1 ~ 1000000이기 때문에 n+1을 매개변수로 넘겨준다.

 

객체의 멤버 변수 중 parent는 해당 노드(?)가 속한 집합의 부모 노드라고 생각하면 이해하기 쉽다.

rank는 초기값이 0인 리스트이고 같은 각 노드의 자식노드의 개수라고 생각하면 이해하기 쉽다.

 

입력 예시를 들어보겠다.

0 1 3 이 입력으로 주어진다면 노드 1과 3은 같은 집합이 된다.
rank 리스트의 인덱스 1번의 값은 1이 되고(1번 노드의 자식 노드의 개수),
parent 리스트의 인덱스 3번은 1이 된다. (3번 노드의 부모 노드는 1번)

1 1 3 이 입력으로 주어진다면 parent리스트의 인덱스 1번과 3번 값이 같기 때문에 "YES"가 출력된다.

 

결과

---

약간의 실수가 있었지만, 정답률 29% 문제 치고 잘 풀었다고 생각한다. ^0^
(사실 디스조인트 셋을 안다면 쉬운 문제다!)

아래는 광고 테스트 용 글이니 더 보기 누르면 안됩니다!

광고용 태그

프로그래밍

알고리즘

컴퓨터

컴퓨터 언어

C언어

파이썬

데이터베이스

인공지능

딥러닝

키보드