[SWEA] 7465 창용 마을 무리의 개수 (Union-Find)

AngJ·2026년 10월 4일

SWEA Union Find 알고리즘

코딩테스트

목록 보기

19/20

문제

SWEA_7465_창용 마을 무리의 개수

요약

1~N 번의 번호를 가진 사람이 있을 때, 각 사람들의 인간관계를 연결해서 무리를 만들어야한다.
최종적으로, 받은 입력으로 만들어지는 전체 무리 개수를 출력해야한다.

접근

무리를 만들어서 총 몇개의 무리로 구성되어있는지를 구하는 문제이니 Union-Find를 사용했다.

Union-Find란?

서로소 집합 알고리즘으로, 교집합이 없는 집합의 개수를 구할 수 있는 알고리즘이다.
이를 위해선 총 3단계로 연산된다.
1. Make-Set(x) : 원소가 본인을 부모로 갖는 서로소 집합으로 초기화
2. Find-Set(x) : 집합 찾기 (대표자를 리턴)
3. Union(x, y) : 두 집합 합치기 (집합과 집합을 합친다)

알고리즘

Parent 배열을 각 원소 번호로 초기화 (Make-Set)
2개의 원소들을 입력 받으며 두 원소들의 대표자를 각각 찾는다. (Find-Set)
각 대표자들이 다르다면 하나의 대표자를 다른 대표자로 바꾼다. (Union)

직접 작성한 수도코드

1. makeset
각 정점을 자신을 부모로 갖도록 부모배열 상태를 초기화한다.

2. findset
선택된 정점의 부모를 찾아간다.

int findSet(int v) {
    if (v == parent[v]) return v;
    return findSet(parent[v])

3. union
두 정점의 크기 비교를 통해 큰놈 밑에 작은 놈을 붙인다.
void union(int x, int y) {
    int parentX = findSet(x);
    int parentY = findSet(y);
    if (parentX == parentY) return;
    if (parentX < parentY) {
        parent[parentY] = parentX;
    }
    else {
        parent[parentX] = parentY;
    }
}

제출코드

import java.io.*;
import java.util.*;

public class Solution {
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken()); // 노드 수
            int M = Integer.parseInt(st.nextToken()); // 간선의 수

            parent = new int[N+1];

            // make-set
            for (int i = 1; i <= N; i++) {
                parent[i] = i;
            }

            for (int m = 0; m < M; m++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                // union
                union(x, y);
            }

            // 무리 개수 출력
            // 무리 개수는 본인이 대표자인 애들만 세면 된다! (중요!)
            int groupCnt = 0;
            for (int i = 1; i <= N; i++) {
                if (parent[i] == i) groupCnt++;
            }

            sb.append("#").append(tc).append(" ").append(groupCnt).append("\n");
        }
        System.out.print(sb.toString());
    }

    // // find-set (경로 압축 x)
    // static int findSet(int v) { // int를 리턴!
    //     if (v == parent[v]) return v;
    //     return findSet(parent[v]);
    // }

    // find-set (경로 압축 o)
    static int findSet(int v) {
        if (parent[v] == v) return v;
        return parent[v] = findSet(parent[v]); // 경로 압축!
    }
	
    // union
    static void union(int x, int y) {
        int parentX = findSet(x);
        int parentY = findSet(y);
        // if (parentX == parentY) return;
        // (중요) 작은 부모의 값을 큰 부모의 값으로 옮긴다! (x와 y를 옮기는게 아니라!)
        if (parentX != parentY) { // 굳이 parentX와 parentY의 대소비교를 하지 않아도 된다! (문제에서 다른 조건이 주어진다면 여기서 집합의 부모를 대소비교 로직 추가하면 된다!)
            parent[parentY] = parentX;
        }
    }       
}

어려웠던 점

마지막에 서로소 집합의 개수를 구할 때, boolean 배열에 parent[v] == v로 T/F로 구분한 뒤, boolean 배열을 순회하면서 true인 애들만 카운트 하는걸로 처음에 개수를 구했는데, 이는 비효율적인 것!

그냥, parent[i] == i인 애들만 카운트하면 된다...
대표자를 바꿨어야하는데, 그냥 입력으로 받은 x를 y로 치환해서 테케 4개를 틀렸다. (절대 까먹지 말 것!)
parent[x] = y 가 아니라!
parent[parentX] = parentY!!
경로 압축!!
find-set 코드의 리턴에 parent[x] = findSet(parent[x])로 업데이트 치는 코드로 바꿔주면 된다!

경로 압축하지 않은 최종 그래프	경로 압축한 최종 그래프

input

배운 점

서로소 집합을 구해야할 땐, Union-Find!
이는 추후 크루스칼 알고리즘을 구현할 때, 활용된다!
return parent[v] = findSet(parent[v]); 는 int를 반환한다! (아래의 식으로 컴파일러가 연산하기 때문)
```
	➡️ int root = findSet(parent[v]);
		parent[v] = root;
  		return root;
```