백준 4195번
https://www.acmicpc.net/problem/4195

문제

---

생각하기

---

• Union-Find 문제이다.

• 친구 이름을 Map에 key 값으로 저장하고 index를 value로 해서 node의 번호 관리한다.

동작

            String f1 = st.nextToken();
            String f2 = st.nextToken();


            if (!map.containsKey(f1)) {
                map.put(f1, idx++);
            }

            if (!map.containsKey(f2)) {
                map.put(f2, idx++);
            }

이름을 입력받고 map에 이름이 존재하지 않으면, index 값을 부여하고 1씩 증가시키며 노드 번호로 관리하게 된다.

    public static int union(int node1, int node2) {
        int node1Parent = find(node1);
        int node2Parent = find(node2);

        if(node1Parent == node2Parent) {
            return cost[node1Parent];
        }

        parents[node1Parent] = node2Parent;
        cost[node2Parent] += cost[node1Parent];
        cost[node1Parent] = 1;

        return cost[node2Parent];
    } // End of union()

union()을 통해서 노드들의 합치는데

node1Parent와 node2Parent의 최상위 노드가 같을 경우 이미 같은 집합 안에 있으므로cost[]의 값을 그대로 출력한다.

만약 node1Parent 와 node2Parent가 다를 경우 node1Parent의 부모가 node2Parent가 되도록 만들어주고,
cost[node2Parent]의 값에 node1Parent가 가지고 있던 union의 크기를 추가한다.

그리고 node1Parent의 사이즈는 다시 1이 되었으므로 초기화를 해준다.
이후 cost[node2Parent]를 return 하면된다.

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, idx;
    private static int[] parents;
    private static int[] cost;
    private static Map<String, Integer> map;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            input();

            bw.write(solve());
        }

        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            String f1 = st.nextToken();
            String f2 = st.nextToken();


            if (!map.containsKey(f1)) {
                map.put(f1, idx++);
            }

            if (!map.containsKey(f2)) {
                map.put(f2, idx++);
            }

            int ret = union(map.get(f1), map.get(f2));
            sb.append(ret).append('\n');
        }

        return sb.toString();
    } // End of solve()

    public static int union(int node1, int node2) {
        int node1Parent = find(node1);
        int node2Parent = find(node2);

        if(node1Parent == node2Parent) {
            return cost[node1Parent];
        }

        parents[node1Parent] = node2Parent;
        cost[node2Parent] += cost[node1Parent];
        cost[node1Parent] = 1;

        return cost[node2Parent];
    } // End of union()

    public static int find(int n) {
        if (parents[n] == n) {
            return n;
        }
        return parents[n] = find(parents[n]);
    } // End of find()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        idx = 0;

        map = new HashMap<>();

        parents = new int[N * 2];
        cost = new int[N * 2];
        for (int i = 0; i < N * 2; i++) {
            parents[i] = i;
            cost[i] = 1;
        }
    } // End of input()
} // End of Main class