[SWEA][D4][#05248] 그룹나누기

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

수업에서 같은 조에 참여하고 싶은 사람끼리 두 사람의 출석 번호를 종이에 적어 제출하였다.

한 조의 인원에 제한을 두지 않았기 때문에, 한 사람이 여러 장의 종이를 제출하거나 여러 사람이 한 사람을 지목한 경우 모두 같은 조가 된다.

예를 들어 1번-2번, 1번-3번이 같은 조가 되고 싶다고 하면, 1-2-3번이 같은 조가 된다. 번호를 적지도 않고 다른 사람에게 지목되지도 않은 사람은 단독으로 조를 구성하게 된다.

1번부터 N번까지의 출석번호가 있고, M 장의 신청서가 제출되었을 때 전체 몇 개의 조가 만들어지는지 출력하는 프로그램을 만드시오.

입력

첫 줄에 테스트 케이스의 개수가 주어지고, 다음 줄부터 테스트 케이스 별로 첫 줄에 N과 M, 다음 줄에 M 쌍의 번호가 주어진다. 2<=N<=100, 1<=M<=100

출력

각 줄마다 “#T” (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예제

입력

3
5 2
1 2 3 4
5 3
1 2 2 3 4 5
7 4
2 3 4 5 4 6 7 4

출력

#1 3
#2 2
#3 3

My Sol

def find_set(x):
    if x!=p[x]:
        p[x] = find_set(p[x])
    return p[x]

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    arr = list(map(int, input().split()))
    p = list(range(N+1))
    for i in range(M):
        u, v = arr[i*2], arr[i*2+1]
        a = find_set(u)
        b = find_set(v)
        if a==b: continue
        p[a] = b
        N -= 1

    print(f'#{tc} {N}')

크루스칼 알고리즘의 서로소 집합을 확인하는 방식을 이용한다. 즉, 새로 들어오는 두 노드의 루트 노드가 같다면 같은 집합 내에 있는 것이고, 이는 다른 집합과 묶이는 것이 아니기 때문에 넘어가는 것이다.

만약 다른 루트 번호라면, 각자 동떨어져있는 분리된 트리인데, 이들을 같은 루트번호로 묶어줄 것이므로 그룹의 수가 1 줄어들게 된다.

즉, 최초의 그룹 개수인 N부터 시작해 다른 루트번호를 가진 관계가 입력되면 같은 루트번호로 처리해주고, N을 1 줄여주다가 모든 입력이 끝나면 N을 출력하면 되겠다.

결과

PASS