백준 4195번 친구 네트워크 :: 마이구미

이 글은 백준 알고리즘 문제 4195번 "친구 네트워크" 를 풀이한다.

풀이 방법으로는 디스조인트-셋을 통해 진행된다.

문제 링크 - https://www.acmicpc.net/problem/4195

디스조인트 셋 이해 - http://mygumi.tistory.com/246

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

노드를 친구로, 간선을 친구 관계라고 생각할 수 있다.

친구 관계라는 것은 같은 트리라고 단순하게 볼 수 있다.

그렇다는건, 서로 다른 친구 관계가 아닐 경우를 생각하면, 각각 다른 트리로 구성되어 있다.

그러다가 친구 관계로 연결될 경우, 하나의 트리로 만들어진다.

주어진 입력으로 인한 위와 같은 흐름을 그림을 통해 확인해보자.

3
Fred Barney
Betty Wilma
Barney Betty

Fred Barney 의 경우는 다음과 같다.

Betty Wilma 의 경우는 다음과 같다.

Barney Betty 의 경우는 다음과 같다.

위와 같이, 경우에 따라, 트리를 만들거나, 연결시켜주면 된다.

기본적인 디스조인트-셋을 이용할 수 있다.

입력이 문자열로 주어지는 것 이외에는 크게 어려울 것이 없다.

실제로는 위와 같은 접근 방법이 동일할 뿐, 루트 노드를 이용하기 때문에, 그림처럼 트리가 만들어지지는 않는다.

결론적으로, 서로 다른 트리를 연결시켜주면 된다. 연결은 트리를 합치는 것과 동일한 의미가 된다.

*여기서 level 배열은 사용하지 않아도 된다. 하지만 이해에 있어, 합쳐지는 과정이 조금 더 직관적이고, 맞는 흐름이다.

링크 - 디스조인트-셋 문제 카테고리 

Github - https://github.com/hotehrud/acmicpc/tree/master/algorithm/disjoint-set

static int parent[];
static int level[];
static int relation[];
static StringBuilder sb;
 
private void solve() {
    int t = sc.nextInt();
    sb = new StringBuilder();
    while (t-- > 0) {
        int f = sc.nextInt();
        int idx = 1;
        HashMap<String, Integer> hm = new HashMap<>();
        parent = new int[200001];
        level = new int[200001];
        relation = new int[200001];
 
        for (int i = 1; i < 200001; i++) {
            parent[i] = i;
            relation[i] = 1; 
        }
 
        for (int i = 0; i < f; i++) {
            String a = sc.next();
            String b = sc.next();
 
            if (!hm.containsKey(a)) {
                hm.put(a, idx++);
            }
 
            if (!hm.containsKey(b)) {
                hm.put(b, idx++);
            }
 
            int ai = hm.get(a);
            int bi = hm.get(b);
 
            merge(ai, bi);
        }
    }
    System.out.println(sb.toString());
}
 
public static void merge(int u, int v) {
    u = find(u);
    v = find(v);
 
    if (u == v) {
        sb.append(relation[u] + "\n");
        return;
    }
 
    if (level[u] > level[v]) {
        int temp = u;
        u = v;
        v = temp;
    }
 
    parent[u] = v;
    relation[v] += relation[u];
    sb.append(relation[v] + "\n");
 
    if (level[u] == level[v]) {
        ++level[v];
    }
}
 
public static int find(int u) {
    if (u == parent[u]) {
        return u;
    }
    return parent[u] = find(parent[u]);
}