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

문제

---

생각하기

---

• 유니온 파인드 문제이다.

• 노드 번호를 자연스럽게 증가하도록 하고 노드 번호에 따른 문제를 HashMap에 저장했다.

동작

        N = Integer.parseInt(br.readLine());
        parents = new int[N * 2];
        ranks = new int[N * 2];
        size = new int[N * 2];

들어오는 간선이 N개인데 노드가 2개씩 들어오는데 들어오는 모든 노드가 각기 다를 경우 최대 N * 2의 크기가 됨

            String nodeA = st.nextToken();
            String nodeB = st.nextToken();

            if (!map.containsKey(nodeA)) {
                map.put(nodeA, nodeNum);
                parents[nodeNum] = nodeNum;
                size[nodeNum] = 1;
                nodeNum++;
            }

            if (!map.containsKey(nodeB)) {
                map.put(nodeB, nodeNum);
                parents[nodeNum] = nodeNum;
                size[nodeNum] = 1;
                nodeNum++;
            }

노드를 번호로 관리하려고 하는데, 문자열로 들어오기 때문에 HashMap에 노드 번호와 문자열을 key, value로 저장한다.

노드 번호는 자동으로 증가시킨다. map에 저장되어 있지 않은 문자열인 경우에만 노드번호를 저장하고, 이미 있는 경우에는 그냥 map에서 꺼내 쓰면된다.

그리고 union()메소드로 노드를 합친 후 결과를 뽑아낼때는 꼭 find()메소드를 통해서 해당 노드의 최상위 부모를 다시 찾은 후
해당 값으로 결과를 뽑아내야 한다.

결과

코드

---

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;
    private static int[] parents, ranks, size;

    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();

        Map<String, Integer> map = new HashMap<>();
        int nodeNum = 1;

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

            if (!map.containsKey(nodeA)) {
                map.put(nodeA, nodeNum);
                parents[nodeNum] = nodeNum;
                size[nodeNum] = 1;
                nodeNum++;
            }

            if (!map.containsKey(nodeB)) {
                map.put(nodeB, nodeNum);
                parents[nodeNum] = nodeNum;
                size[nodeNum] = 1;
                nodeNum++;
            }

            union(map.get(nodeA), map.get(nodeB));
            sb.append(size[find(map.get(nodeA))]).append('\n');
        }

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

    private static void union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if (aRoot == bRoot) return;

        if (ranks[aRoot] < ranks[bRoot]) {
            parents[aRoot] = bRoot;
            size[bRoot] += size[aRoot];
        } else {
            parents[bRoot] = aRoot;
            size[aRoot] += size[bRoot];
            if (ranks[aRoot] == ranks[bRoot]) {
                ranks[aRoot]++;
            }
        }
    } // End of union()
    
    private static int find(int node) {
        if (parents[node] == node) return node;

        return parents[node] = find(parents[node]);
    } // End of find()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        parents = new int[N * 2];
        ranks = new int[N * 2];
        size = new int[N * 2];
    } // End of input()
} // End of Main class