[알고리즘 / 백준] 4195 - 친구 네트워크

문제는 위와 같습니다. 저한테는 조금 난이도가 있었던 문제였습니다.

먼저 이 문제는 Union-Find 알고리즘을 사용하였습니다. Union-Find 알고리즘은 Disjoint Set을 표현하기 위한 알고리즘인데, Disjoint Set 은 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조로 서로소 집합 자료구조입니다.

 

이 문제를 해결하기 위해 딕셔너리 타입으로 자신(key)과 연결된 대표 노드(value)를 표현하고, 새로운 조합이 들어올 때마다 각각의 대표 노드(부모 노드)를 찾아서(Find) 다른 쪽의 부모 노드로 연결(Union)해 주면서 union 과 find 를 반복하는 것입니다. 또한 이때 연결되는 노드의 수를 알아야하기 때문에 이를 표현하는 딕셔너리를 하나 더 추가하여 구현하였습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin


def find(p):
    if p == parent[p]:
        return p
    else:
        pp = find(parent[p])  # 최상위 부모 노드 찾기
        parent[p] = pp
        return parent[p]


def union(p1, p2):
	# 부모 노드 찾기
    parent1 = find(p1)
    parent2 = find(p2)

	# 두 노드의 부모 노드가 다른 경우 (연결이 안되어 있는 경우)
    if parent1 != parent2:
        parent[parent2] = parent1  # 두번째 노드의 부모 노드로 첫번째 노드를 지정
        number[parent1] += number[parent2]  # 연결된 노드 수도 증가


test_case = int(stdin.readline())
for _ in range(test_case):
    parent = dict()
    number = dict()
    F = int(stdin.readline())
    for _ in range(F):
        person1, person2 = stdin.readline().split()

		# 한번도 연결된 적 없는 노드인 경우 자기 자신을 부모 노드로 지정
        if person1 not in parent:
            parent[person1] = person1
            number[person1] = 1

        if person2 not in parent:
            parent[person2] = person2
            number[person2] = 1

		# 두 노드를 연결
        union(person1, person2)

        print(number[find(person1)])

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static Map<String, String> parent = new HashMap<>();
    static Map<String, Integer> networks = new HashMap<>();

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

        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            parent.clear();
            networks.clear();

            int f = Integer.parseInt(br.readLine());
            for (int j = 0; j < f; j++) {
                String[] people = br.readLine().split(" ");

                if (!parent.containsKey(people[0])) {
                    parent.put(people[0], people[0]);
                    networks.put(people[0], 1);
                }

                if (!parent.containsKey(people[1])) {
                    parent.put(people[1], people[1]);
                    networks.put(people[1], 1);
                }

                union(people[0], people[1]);
                System.out.println(networks.get(find(people[0])));
            }
        }
    }

    private static String find(String p) {
        if (p.equals(parent.get(p))) {
            return p;
        }

        String par = find(parent.get(p));
        parent.put(p, par);
        return parent.get(p);
    }

    private static void union(String a, String b) {
        String parent1 = find(a);
        String parent2 = find(b);

        if (!parent1.equals(parent2)) {
            parent.put(parent2, parent1);
            networks.put(parent1, networks.get(parent1) + networks.get(parent2));
        }
    }
}