[Algorithm] 백준 유니온파인드 문제 - 친구 네트워크(4195) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준 친구 네트워크 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

1. 풀이 소스

 

import java.io.*;
import java.util.HashMap;
import java.util.Map;

import static java.lang.Integer.parseInt;

public class Main {

    static int[] parent; // 부모 노드 설정
    static int[] cnt; // 부모에 있는 노드의 자식 노드 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = parseInt(br.readLine());
        for (int i = 0; i < t; i++) {

            Map<String, Integer> map = new HashMap<>(); // 각 이름과 인덱스를 저장할 map
            int n = parseInt(br.readLine()); // 배열을 초기화할 개수

            // n개의 연결관계가 있으므로 n * 2가 최대
            parent = new int[n * 2];
            cnt = new int[n * 2];

            for (int j = 0; j < parent.length; j++) {
                parent[j] = j; // 부모 노드 자신으로 초기화
                cnt[j] = 1; // 개수는 모두 1로 초기화
            }

            int idx = 0; // 인덱스 0 설정
            for (int j = 0; j < n; j++) {
                String[] str = br.readLine().split(" ");

                if (!map.containsKey(str[0])) map.put(str[0], idx++);
                if (!map.containsKey(str[1])) map.put(str[1], idx++);

                union(map.get(str[0]), map.get(str[1])); // 두 친구 연결하기
                sb.append(cnt[find(map.get(str[1]))]).append("\n"); // 두번째 인원의 부모를 찾아서 네트워크 연결된 수 찾기
            }
        }

        System.out.print(sb);
    }

    static int find(int child) { // find
        if (parent[child] == child) return child;
        return parent[child] = find(parent[child]); // 경로 압축
    }

    static void union(int c1, int c2) { // 합치기
        int p1 = find(c1); // c1의 부모 노드 
        int p2 = find(c2); // c2의 부모 노드

        if (p1 == p2) return;
        parent[p2] = p1;
        cnt[p1] += cnt[p2]; // p1의 자식 노드 수 p2의 자식 노드 수 합치기
        cnt[p2] = 0; // p2 인원 초기화
    }
}

 

2. 풀이 중점 사항

 

친구 네트워크는, 서로 다른 집합의 네트워크가 분산되어 있을 때, 하나로 연결하는 작업을 수행해야 합니다.

이렇게 서로 다른 집합을 서로 연결해야 하는 문제가 주어졌을 때, 적용할 수 있는 알고리즘이 유니온 파인드입니다.

 

static int find(int child) { // find
    if (parent[child] == child) return child;
    return parent[child] = find(parent[child]); // 경로 압축
}

static void union(int c1, int c2) { // 합치기
    int p1 = find(c1); // c1의 부모 노드 
    int p2 = find(c2); // c2의 부모 노드

    if (p1 == p2) return;
    parent[p2] = p1;
}

 

부모 노드에 속한 자식 노드 개수 구하기

 

p1, p2의 노드를 유니온 파인드 진행할 때, p1의 부모 노드의 자식 노드의 개수와 p2의 부모 노드의 자식 노드 개수를 모두 더해야 합니다. 이를 구현하기 위해 cnt 배열을 선언하였습니다.

 

자식 노드의 개수를 늘리는 로직은 union을 수행할 때 적용할 수 있습니다.

만약 두 부모 노드가 다르다면, 부모 노드 중 합쳐서 집합이 더 커진 대상을 기준으로 합쳐진(합쳐져서 없어진 집합)의 자식 노드 수를 더해줍니다. 

 

parent[p2] = p1;
cnt[p1] += cnt[p2]; // p1의 자식 노드 수 p2의 자식 노드 수 합치기
cnt[p2] = 0; // p2 인원 초기화

 

이상으로 자바 친구 네트워크 풀이를 마치도록 하겠습니다. 감사합니다.