[python] SWEA 5248 : 그룹 나누기

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

1. 코드 구현 (deque 사용)

from collections import deque

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

def union(parent, x, y):
    x = find(parent, x)
    y = find(parent, y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

for tc in range(1, int(input())+1):
    n, m = map(int, input().split())
    data = list(map(int, input().split()))
    q = deque(data)
    parent = [i for i in range(n+1)]

    while q:
        a = q.popleft()
        b = q.popleft()
        union(parent, a, b)
    result = set()
    for i in range(1, n+1):
        data = find(parent, i)
        result.add(data)

    print(f'#{tc} {len(result)}')

 

 

2. 코드 구현 (for문 사용)

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

def union(parent, x, y):
    x = find(parent, x)
    y = find(parent, y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

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

    for i in range(0, 2*m, 2):
        union(parent, data[i], data[i+1])
    result = set()
    for i in range(1, n+1):
        data = find(parent, i)
        result.add(data)

    print(f'#{tc} {len(result)}')

 

서로소 부분 집합을 가지고 서로소 집합을 만들기 위한 자료구조 : union + find 

서로소 집합 : {1,3,5} {2,7,9}

서로소 부분집합 : {1,3} {3,5} {7,2} {7,9}

union : 각 원소가 포함된 집합을 하나로 합치기 

find : 속한 집합의 루트 노드 찾기 (부모 노드를 통해 어떤 집합에 속했는지 확인 가능)

1. 부모 테이블 자기 자신으로 초기화

2. 주어진 두 노드에 대해 union 진행

3. 2번 반복