[SWEA] 창용 마을 무리의 개수

# Union-Find

#DFS

 

문제

창용 마을에는 N명의 사람이 살고 있다.

사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.

두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수도 있다.

두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 모두 묶어서 하나의 무리라고 한다.

창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.

 

 

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는
두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다.
이후 M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호가 주어진다. 같은 관계는 반복해서 주어지지 않는다.

 

입력	출력
2 6 5 1 2 2 5 5 1 3 4 4 6 6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3	#1 2 #2 1

 

---

풀이

 

첫번째 tc의 경우, 

이어서 붙이면 다음과 같이 그룹이 두개 생긴다.

이렇게 각각 그룹을 만들어서 총 그룹의 갯수를 출력하면 됨!

 

그래서...

Union Find를 써서 parent를 정리한 후

서로 다른 parent의 갯수를 구해주면 된다.

 

# Union-Find

def find(x):
    if x == parent[x]:
        return x
    else:
        return find(parent[x])
 
T = int(input())
for tc in range(1, T + 1):
    N, M = map(int,input().split())
    parent = [i for i in range(N + 1)]
    arr = [list(map(int,input().split())) for _ in range(M)]
    for a, b in arr:
        parent[find(a)] = find(b)
 
    ans = 0
    for i in range(1, N + 1):
        if i == parent[i]:
            ans += 1
    print(f'#{tc} {ans}')

다음과 같이 구현했다.

처음엔 union 함수도 써봤는데 그냥 바로 두 사람의 부모를 맞춰주는 걸로 해결했다.

확인하는 용도로는 parent에서 자기 자신이 부모라면 갯수를 늘려주는 걸로

 

 

 

 

다른 방법도 없을까 싶어서 DFS로도 해봤다.

# DFS

def DFS(start):
    global cnt
    stack = [start]
    while stack:
        now = stack.pop()
        for next_people in arr[now]:    # 지금 사람의 친구들 중
            if visited[next_people] == 0:   # 안들린 사람이라면
                visited[next_people] = 1    # 방문처리
                stack.append(next_people)
    cnt += 1     # 함수 다 돌렸다면 그룹갯수 +1

T = int(input())
for tc in range(1, T + 1):
    N, M = map(int,input().split())
    arr = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int,input().split())
        arr[a].append(b)    
        arr[b].append(a)    # 양방향
    visited = [0 for _ in range(N + 1)]
    cnt = 0     # 그룹의 갯수
    for i in range(1, N + 1):
        if visited[i] == 0:     # 확인 안한 사람만 dfs를 돌려줌
            DFS(i)
    print(f'#{tc} {cnt}')

 

---

• DFS 연습 더 하자...
• Union Find 너무 어렵다. 개념 제대로 다시 정리 한번 해야할것같다