[SWEA 5248번] 그룹 나누기 - 파이썬(python)

SW Expert Academy

문제

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

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

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

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

입력

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

출력

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

풀이

• 유니온 파인드를 이용하여 각자의 부모를 찾아서 채운다.
• 처음에는 테스트 케이스에 부모 자식의 관계가 하나인 경우라서 set을 사용하여 중복되는 수를 제거하고 숫자를 구했다.
• 하지만 그럴 경우에는 부모 자식 자손의 관계가 존재할 경우를 표현하지 못하는 문제가 발생했다.
• 따라서 부모 배열을 자기자신이 아닌 0으로 채우고 이후에 0의 개수를 세는 방향이 있다.(0인 수는 루트노드, 리스트의 0번 인덱스는 사용하지 않으므로 -1)
• 아니면 부모가 다른 경우만 union 함수를 실행하고 함수를 실행하고 나면 두 함수의 부모가 같아지게 되어 하나의 그룹으로 합쳐지게 되므로 총인원 N에서 union할 때마다 -1을 해주고 최종 N의 값이 그룹의 개수가 된다.

코드

# 부모찾기
def Find(n):
    if parent[n] != 0:
        return Find(parent[n])
    return n

def union(a, b):
    a = Find(a)
    b = Find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

T = int(input())
for test_case in range(1, T + 1):
    # N: 출석 번호, M: 신청서 장수
    N, M = map(int, input().split())
    # 신청서 리스트
    lst = list(map(int, input().split()))
    # 부모 리스트(초기값)
    parent = [0]*(N+1)
    # 부모 찾기
    for i in range(0, M * 2, 2):
        if Find(lst[i]) != Find(lst[i + 1]):
            union(lst[i], lst[i + 1])
            # union find를 하면 리스트 중 하나가 합쳐진 것이므로 번호N-1
            N-=1
    # 리스트parent에 있는 0이 루트노드이므로 0의 개수를 센다.
    rlt = parent.count(0)
    print(f'#{test_case} {N}')
    # parent[0]의 0은 사용하지 않으므로 rlt-1이 정답
    print(f'#{test_case} {rlt-1}')