그룹 나누기 Python(SW Expert Academy, SWEA)

난이도 : D3

문제번호 : 5248

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYG3y62EcDFAVT#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

수업에서 같은 조에 참여하고 싶은 사람끼리 두 사람의 출석 번호를 종이에 적어 제출하였다. 한 조의 인원에 제한을 두지 않았기 때문에, 한 사람이 여러 장의 종이를 제출하거나 여러 사람이 한 사람을 지목한 경우 모두 같은 조가 된다. 예를 들어 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

---

2. 문제풀이

문제를 보면 내가 어떤사람을 지목했을때 그사람이 조에 들어가있다면 그 조에 포함된다 입니다. 보자마자 아! Union Find구나 하고 생각합니다. 부모를 저장하는 배열을 만든뒤에 조가 만들어질때 작언 번호를 가진쪽으로 부모를 병합하는 과정으로 문제를 풀어나갑니다. 부모를 찾을때는 재귀를 이용하여 찾도록 합니다. 마지막에 데이터가 최신화 되어있지 않을수도 있기때문에 set을 만들어 모든 부모노드를 넣어줍니다. 부모가 다를경우 다른 조라고 판단합니다. 부모를 표시하는 리스트를 만들때 저는 N+1까지 만들었기 때문에 set에 0이 추가됩니다. 따라서 결과값을 출력할때 -1을 해줍니다.

 

---

3. 소스코드

#D3 5248 그룹 나누기
 
def get_parent(x):
    if parent[x] != x: parent[x] = get_parent(parent[x])
    return parent[x]
 
def union_parent(x, y):
    a = get_parent(x)
    b = get_parent(y)
    if a > b: parent[a] = b
    else: parent[b] = a
 
for t in range(int(input())):
    N, M = map(int, input().split())
    parent = [i for i in range(N+1)]
    votes = list(map(int, input().split()))
    for i in range(0, M*2, 2): union_parent(votes[i], votes[i+1])
    answer = set()
    for i in parent: answer.add(get_parent(i))
    print('#{} {}'.format(t+1, len(answer)-1))