[백준] 1717번 집합의 표현 Python 파이썬 풀이

---

1717번: 집합의 표현

---

[문제]

---

[코드]

 

import sys

sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

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


for _ in range(m):
    command, a, b = map(int, input().split())
    if command == 0:
        union_parent(a, b)
    else:
        if find_parent(a) == find_parent(b):
            print("YES")
        else:
            print("NO")

---

[해설]

백준의 자료구조 문제중 골드4에 해당하는 문제이다.

초반 구조 설계만 잘한다면 쉽게 풀수 있는 문제이다.

 

이 문제의 핵심은 다음과 같다

 1. 두 집합이 어디에 속해있는 찾는 방법
 2. 두 집합을 합치는 방법

 

import sys

sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

재귀함수를 활용할 것이기 때문에 재귀함수의 깊이를 지정해준다.

그리고 n,m 변수를 받아주고

처음 parent 리스트를 생성하여 초기 집합을 구성해준다.

 

ex) 출력1 

parent = [ [0], [1], [2], [3] ... [7] ]

 

 

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

첫 번째로 만들어 줄 함수는 find_parent이다.

즉, 부모 집합을 탐색해주는 함수이다.

 

만약 parent[x]가 x와 같다면 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

이 부분은 2번째 문제인 합집합을 만드는 함수로 

부모를 찾고 이를 통해서 b가 크다면 parent[b]의 부모를 a로 지정하고 다른 경오 parent[a]의 부모를 b로 지정하는것이다.

 

두 함수를 적용해서 

예를 들어 쉽게 설명하자면 

ex) 예제1

i) 

초기 parent

x	0	1	2	3	4	5	6	7
부모	0	1	2	3	4	5	6	7

0 1 3

0 = 합집합 (union_parent(1, 3)

find_parent(1) == 1

find_parent(3) == 3

따라서 

parent[3] == 1

x	0	1	2	3	4	5	6	7
부모	0	1	2	1	4	5	6	7

 

ii)

1 1 7

1 = 부모가 같은지 판단

find_parent(1) == 1

find_parent(7) == 7

1 != 7

따라서 No

 

이런식으로 부모와 x값이 다른 경우에는 다시 재귀를 통해서 부모값의 부모를 찾아가면된다.

 

위 메커니즘이 이 문제의 핵심이다.

 

따라서 이러한 계산을 반복하여 

for문으로 표현하면 아래와 같다

for _ in range(m):
    command, a, b = map(int, input().split())
    if command == 0:
        union_parent(a, b)
    else:
        if find_parent(a) == find_parent(b):
            print("YES")
        else:
            print("NO")

command가 0일경우 합집합을 만들고

1 일경우 a,b의 부모를 비교하여 같은 경우 YES를

다른경우 NO를 출력한다.