[SWEA/Python] 5248. 그룹 나누기

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 하나의 조를 집합으로 생각하고 각 집합마다 집합을 대표하는 수를 parents에 저장한다. (초기값은 자기자신)
2. 입력 값에 따라 union함수를 실행시켜서 집합을 합친다.
3. 모든 조를 다 짠 후, 전체 원소에 대해 find_set 함수를 실행해서 대표 숫자를 업데이트 해준다.
4. 대표 숫자를 set으로 만들어서 중복값을 없애주고 길이를 출력하면 완성된 조의 숫자가 된다.
   (parents에 0도 포함되므로 1은 빼준다.)

 

📌 코드

import sys
sys.stdin = open('input.txt')

def find_set(x):
    if x != parents[x]:
        parents[x] = find_set(parents[x])

    return parents[x]


def union(x, y):
    root_x = find_set(x)
    root_y = find_set(y)

    # root_x의 트리의 높이가 더 크거나 같을 경우
    if ranks[root_x] >= ranks[root_y]:
        parents[root_y] = root_x
        # 만약에 높이가 같다면 rank 증가
        if ranks[root_x] == ranks[root_y]:
            ranks[root_y] += 1
    # root_y의 트리의 높이가 더 클 경우
    else:
        parents[root_x] = root_y


T = int(input())

for t in range(1, T+1):
    N, M = map(int, input().split())
    paper = list(map(int, input().split()))

    parents = [x for x in range(N+1)]
    ranks = [0 for _ in range(N+1)]

    for i in range(0, M*2-1, 2):
        union(paper[i], paper[i+1])
    
    for j in range(1, N+1):
        find_set(j)

    print('#{} {}'.format(t, len(set(parents))-1))