창용 마을 무리의 개수

1. 문제 접근 방법 및 아이디어

이 문제는 여러 명의 사람이 있고, 그들 사이의 관계가 주어질 때, 총 몇 개의 독립된 그룹이 형성되는가?를 구합니다.

1. 초기화
   • 각 사람을 하나의 독립된 집합으로 간주합니다. (자신이 자신의 대표자)
2. 관계 파악
   • 두 사람이 아는 관계라면, 두 사람이 속한 집합을 하나로 합칩니다. (Union)
3. 그룹 카운팅
   • 모든 관계를 확인한 후, 서로 다른 대표자(루트 노트)가 몇 명인지 세어 무리의 개수를 구합니다.

2. 필요 개념 및 알고리즘

1. Union-Find 알고리즘
   • 여러 요소가 하나의 집합에 속해 있는지 확인하고, 필요시 합치는 작업에 최적화된 알고리즘이 Union-Find입니다.
   • A와 B가 알고, B와 C가 알면 A와 C도 아는 사이다라는 문구는 전이적 관계를 나타내며, 이는 그래프의 연결성이나 집합의 합집합 개념을 떠올리게 합니다.

3. 어려워하는 포인트와 실수하는 포인트

1. 무리의 개수를 셀 때, 단순히 parent배열의 값을 세는 것이 아니라 최종 부모 루트의 개수를 세어야 한다는 점입니다.
2. 배열 인덱스를 0부터 쓸지 1부터 쓸지 헷갈리는 경우입니다.
3. find함수에서 경로 압축을 빠뜨려 효율성이 떨어지는 경우입니다.

4. 코드 풀이

4.1 Union - Find 구현

4.1.1 변수 선언

static int N, M; // 사람의 수, 사람의 관계 수
static int parent[]; // 부모 노드 체크 배열

• 노드의 수 N, 부모 노드 체크 배열 선언

4.1.2 makeSet 함수

static void makeSet() {
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
}

• 단위 집합을 생성하는 함수 입니다.
• 처음에는 모든 숫자가 각각 자기 자신만을 원소로 갖는 집합을 생성합니다.

4.1.3 findSet 함수

static int findSet(int a) {
    if (a == parent[a])
        return a;
    return parent[a] = findSet(parent[a]);
}

• 종료 조건에서 부모가 자신과 같으면 종료합니다.
• 만약 부모와 자신이 같지 않으면 자신의 부모를 탐색합니다.
• 탐색을 빨리하기 위해 경로 압축을 사용합니다.
  • 자신의 가장 높은 부모를 받아서 저장합니다.

4.1.4 unionSet 함수

static void unionSet(int a, int b) {
    int aRoot = findSet(a);
    int bRoot = findSet(b);
 
    if (aRoot == bRoot)
        return;
 
    parent[bRoot] = aRoot;
 
}

• 두 원소 a,b의 부모 노드를 탐색합니다.
• 두 대표자가 같으면 같은 집합이기 때문에 연결하지 않습니다.
• 두 대표자가 다르면 연결합니다.

4.2 무리 카운팅

for (int i = 1; i <= N; i++) {
    if (parent[i] == i) result++; // 자신이 루트인 경우만 카운트
}

• 무리의 대표자는 parent[i] == i인 상태이기 때문입니다.

4.3 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int N, M; // 사람의 수, 사람의 관계 수
    static int parent[]; // 부모 노드 체크 배열
    static int result; // 무리의 개수
    static boolean check[]; // 중복 체크 배열
 
    // 단위 집합 생성 함수
    static void makeSet() {
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
    }
 
    // 부모 노드 탐색 함수
    static int findSet(int a) {
        if (a == parent[a])
            return a;
        return parent[a] = findSet(parent[a]);
    }
 
    // 집합 연결 함수
    static void unionSet(int a, int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);
 
        if (aRoot == bRoot)
            return;
 
        parent[bRoot] = aRoot;
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine().trim());
 
        // tc 수행
        for (int tc = 1; tc <= T; tc++) {
 
            // N, M 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
 
            // 초기화
            result = 0;
            check = new boolean[N + 1];
            parent = new int[N + 1];
            makeSet();
 
            // 사람의 관계 입력
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
 
                unionSet(a, b);
            }
 
            // 처리
            for (int i = 1; i <= N; i++) {
                if (parent[i] == i) result++; // 자신이 루트인 경우만 카운트
            }
 
            // 출력 내용 추가
            sb.append("#" + tc + " " + result + "\n");
 
        } // tc 종료
 
        // 출력
        System.out.println(sb);
 
    }
 
}