백준 11724번 : 연결 요소의 개수 (유니온 파인드 알고리즘)

1. 문제

https://www.acmicpc.net/problem/11724

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1 복사

6 5
1 2
2 5
5 1
3 4
4 6

 

예제 출력 1 복사

2

예제 입력 2 복사

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

 

예제 출력 2 복사

1

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static boolean[][] lines;
	static boolean[] visited;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(token.nextToken());
		int M = Integer.parseInt(token.nextToken());
		lines = new boolean[N + 1][N + 1];
		visited = new boolean[N + 1];
		for (int i = 0; i < M; i++){
			token = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(token.nextToken());
			int b = Integer.parseInt(token.nextToken());
			lines[a][b] = lines[b][a] = true;
		}
		int count = 0;
		for (int i = 1; i <= N; i++){
			if (!visited[i]){
				count++;
				dfs(i);
			}
		}
		System.out.println(count);
	}
	private static void dfs(int n) {
		visited[n] = true;
		for (int i = 1; i < lines[n].length; i++) {
			if (lines[n][i] && !visited[i]) {
				dfs(i);
			}
		}
	}

}

3. 해설

• dfs 방식을 활용하여 연결된 선을 재귀적 방식으로 모두 방문하고 카운팅한다

4. 다른 풀이

유니온 파인드(Union-Find) 알고리즘 활용

유니온 파인드 알고리즘의 핵심 개념:

 

• Find: 특정 노드가 속한 집합의 루트 노드를 찾음.
• Union: 두 노드를 같은 집합으로 합침 (즉, 두 노드가 같은 연결 요소에 속하도록 만듦).
• Path Compression: Find 연산 시, 트리의 높이를 줄여주는 최적화 방법.
• Union by Rank: 트리의 깊이를 줄이기 위해 작은 트리를 큰 트리에 연결하는 방법.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] parent;
    static int[] rank;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(token.nextToken());
        int M = Integer.parseInt(token.nextToken());

        parent = new int[N + 1];
        rank = new int[N + 1];

        // 각 노드의 부모를 자기 자신으로 초기화하고, 랭크를 0으로 초기화
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
            rank[i] = 0;
        }

        // 간선 정보 입력 및 유니온 처리
        for (int i = 0; i < M; i++) {
            token = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(token.nextToken());
            int b = Integer.parseInt(token.nextToken());
            union(a, b);
        }

        // 연결 요소 개수 세기
        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (find(i) == i) { // 루트 노드일 경우 count 증가
                count++;
            }
        }

        System.out.println(count);
    }

    // Find 함수: 경로 압축을 적용하여 부모를 찾아주는 함수
    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]); // 경로 압축
    }

    // Union 함수: 두 집합을 랭크에 따라 병합
    private static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA != rootB) {
            // 랭크를 비교하여 더 작은 트리를 더 큰 트리 밑에 병합
            if (rank[rootA] > rank[rootB]) {
                parent[rootB] = rootA; // rootB를 rootA 밑에 둠
            } else if (rank[rootA] < rank[rootB]) {
                parent[rootA] = rootB; // rootA를 rootB 밑에 둠
            } else {
                // 랭크가 같으면 아무 쪽이나 병합하고, 병합된 쪽의 랭크를 1 증가시킴
                parent[rootB] = rootA;
                rank[rootA]++;
            }
        }
    }

}

 

• union()을 수행하면 똑같은 root를 바라보게 됨
• find() root를 반환함
  예 : parent[1] = 1, parent[4] = 1, parent[5] = 4 인 상황에서 find(5)를 호출하면 5 → 4 → 1 즉, 1을 반환한다
  이 부분에서 경로 압축이 발생함
• 랭크 개념 :
  • 랭크 = 깊이 라고 생각할 수 있고, 같은 깊이끼리 병합할 때만 깊이가 한칸 깊어지도록 설계한다
  • 만약 다른 랭크 끼리 병합한다면 더 큰 쪽으로 병합해버리면 깊이는 깊어지지 않는다
    예를 들어 랭크 4까지 유니온과 랭크 2짜리 유니온이 병합할 때 2짜리 유니온이 루트아래로 붙어도 깊이는 3밖에 되지 않으니 랭크가 더 깊어지지 않는다.