[백준 4195번] 친구 네트워크 - 상호 배타적 집합(disjoint set), 유니온 파인드

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

종만북의 유니온 파인드 코드를 참조한 풀이입니다.

 

주의할만한 몇 가지 포인트에 대해서만 짚고 가겠습니다.

 

1. 이름을 int형의 id값으로 변환

문자열로는 트리를 구성하기 불편하기 때문에 int형으로 변환했습니다.

 

2. find 연산에서의 경로 최적화

이는 중복 연산을 피하기 위해 트리의 구조를 수정하는 작업입니다. find를 수행할 때마다 루트를 찾음과 동시에 경로에 있는 노드의 parent를 모두 집합의 루트로 수정합니다. 만약 수정된 노드에 대해서 find 연산을 하게 되면 바로 집합의 루트를 반환할 수 있도록 합니다.

 

3. merge 연산에서의 rank 값 비교

rank[i] 의 정의는 다음과 같습니다.

 

rank[i] : id = i인 노드를 루트로 하는 서브 트리의 높이

 

그럼 왜 높이를 나타내는 height라는 단어를 사용하지 rank를 썼냐? 그 이유는 위에서의 경로 최적화로 인해 트리의 구조가 수정되어 집합 트리의 실제 높이가 동적으로 변하기 때문입니다. 그래서 height대신 rank라는 용어를 사용하며, rank는 경로 최적화 전의 트리의 높이를 나타냅니다.

그리고 합치기를 할 땐 반드시 rank 값이 큰 쪽의 루트가 다시 연산 후의 루트가 됩니다. 이렇게 할 경우, rank 값이 작은 서브트리가 더 큰 서브트리에 붙을 때 rank값이 변하지 않습니다. rank값이 서로 같은 서브 트리들이 합쳐질 때에만 rank값이 늘어나게 됩니다. 이런 식으로 트리를 합치게 되면 트리의 구조가 한쪽으로 쏠리는 것을 막을 수 있습니다.

 

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

/*
친구 네트워크
https://www.acmicpc.net/problem/4195
 */
public class Main {
    static int T, N;
    static int[] parent, rank, size;

    public static void main(String[] args) throws IOException {
        InputReader reader = new InputReader();
        T = reader.readInt();
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            N = reader.readInt();
            Map<String, Integer> nameToId = new HashMap<>();
            parent = new int[N+1];
            rank = new int[N+1];
            size = new int[N+1];

            for (int i = 0; i <= N; i++) {
                parent[i] = i;
                rank[i] = 0;
                size[i] = 1;
            }

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(reader.readLine());
                String u_name = st.nextToken(); String v_name = st.nextToken();
                int u_id = mappedToId(u_name, nameToId); int v_id = mappedToId(v_name, nameToId);
//                System.out.printf("tc : %d, u_id : %d, v_id : %d\n",tc, u_id, v_id);
                int size = merge(u_id, v_id);
                sb.append(size).append("\n");
            }
            id = 0;
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb.toString());
    }

    private static int merge(int u_id, int v_id) {
        int u_root = find(u_id); int v_root = find(v_id);

        if(u_root == v_root) return size[u_root];
        if(rank[u_root] > rank[v_root]) {
            int temp = v_root;
            v_root = u_root;
            u_root = temp;
        }
        //항상 높이가 더 큰 서브트리를 v쪽에 두고 합친다.
        parent[u_root] = v_root;
        if(rank[u_root] == rank[v_root]) ++rank[v_root];

        return size[v_root] += size[u_root];
    }

    private static int find(int id) {
        if(id == parent[id]) return id;
        return parent[id] = find(parent[id]); //경로 최적화
    }

    static int id = 0;
    /*
    String 타입인 이름을 Integer 자료형의 id로 변환한다.
     */
    public static int mappedToId(String name, Map<String, Integer> nameToId) {
        if(!nameToId.containsKey(name)) {
            nameToId.put(name, id); id++;
        }
        return nameToId.get(name);
    }
}
class InputReader {
    private BufferedReader br;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public InputReader(String filepath) {
        try {
            br = new BufferedReader(new FileReader(filepath));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public List<Character> readLineIntoCharList() throws IOException {
        List<Character> l = new ArrayList<>();
        while(true) {
            int readVal = br.read();
            if(readVal == '\n' || readVal == -1) break;
            l.add((char)readVal);
        }
        return l;
    }

    public boolean ready() throws IOException {
        return br.ready();
    }

    public String readLine() throws IOException {
        return br.readLine();
    }
    public int readInt() throws IOException {
        return Integer.parseInt(readLine());
    }
    public Long readLong() throws IOException {
        return Long.parseLong(readLine());
    }
}