[SW Expert Academy] 5248. 그룹 나누기

5248. 그룹 나누기

---

문제)

 

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

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

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

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

 

 

[입력]

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

 

 

[출력]

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

 

 

 

 

 

풀이)

플러드 필이 생각나는 문제였다.

 

 

 

 

1번 풀이 // 그리디 하게 풀어보기

 

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    arr = [0] * (n + 1)
    li = list(map(int, input().split()))
 
    num = 1
    for i in range(m):
        a = li[i * 2]
        b = li[i * 2 + 1]
 
        if not arr[a] and not arr[b]:
            arr[a] = num
            arr[b] = num
            num += 1
 
        elif arr[a] and arr[b] and arr[a] != arr[b]:
            x = arr[a]
            y = arr[b]
            for j in range(1, n + 1):
                if arr[j] == x or arr[j] == y:
                    arr[j] = num
            num += 1
        else:
            if arr[a] and not arr[b]:
                arr[b] = arr[a]
            elif li[i * 2 + 1] and not arr[a]:
                arr[a] = arr[b]
 
    com = set(arr)
 
    print(f"#{_ + 1} {arr.count(0) - 1 + len(com) - 1}")

 

 

2번 풀이 // bfs 활용

 

from collections import deque
 
def bfs(a):
 
    queue = deque()
    queue.append(a)
    visited[a] = 1
 
    while queue:
        a = queue.popleft()
 
        for i in g[a]:
            if visited[i]:
                continue
            queue.append(i)
            visited[i] = 1
 
T = int(input())
for _ in range(T):
 
    n, m = map(int, input().split())
    li = list(map(int, input().split()))
    g = [[] for i in range(n + 1)]
    for i in range(m):
        a = li[i * 2]
        b = li[i * 2 + 1]
 
        g[a].append(b)
        g[b].append(a)
 
    visited = [0] * (n + 1)
    cnt = 0
    for i in range(1, n + 1):
        if not visited[i]:
            cnt += 1
            bfs(i)
    print(f"#{_ + 1} {cnt}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.