[Algorithm] 합집합 찾기(Union-Find)

설명

• 서로 다른 두 노드가 같은 그래프에 속하는지를 확인하는 알고리즘

예시

• 노드 1 2 3이 하나의 그래프, 4 5가 또 다른 하나의 그래프에 속할 경우
• 1 2 3 모두 부모는 1
• 4 5 모두 부모는 4
• 1과 3이 같은 그래프인가? → 부모값이 같은지 확인 → 둘다 1 → true
• 1과 5가 같은 그래프인가? → 부모값이 같은지 확인 → 1은 1, 5는 4 → false

코드

public class Solution {
    public boolean solution(int[][] data, int value1, int value2) {
        int maxValue = Arrays.stream(data).map(values -> Math.max(values[0], values[1])).max(Comparator.comparing(value -> value)).get();
        int[] root = new int[maxValue + 1];

        for (int i = 0; i <= maxValue; i++) {
            root[i] = i;
        }

        for (int[] values : data) {
            if (!isSameUnion(root, values[0], values[1])) {
                union(root, values[0], values[1]);
            }
        }

        return root[value1] == root[value2];
    }

    private void union(int[] root, int value1, int value2) {
        int x = find(root, value1);
        int y = find(root, value2);

        if (x < y) {
            root[y] = x;
        } else {
            root[x] = y;
        }
    }

    private boolean isSameUnion(int[] root, int value1, int value2) {
        return find(root, value1) == find(root, value2);
    }

    private int find(int[] root, int value) {
        if (root[value] == value) {
            return value;
        }

        return root[value] = find(root, root[value]);
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data, #value1, #value2 -> #result"() {
        expect:
        new Solution().solution(data as int[][], value1 as int, value2 as int) == result as boolean

        where:
        data                                             | value1 | value2 | result
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 1      | 2      | true
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 2      | 3      | true
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 3      | 5      | false
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 4      | 7      | false
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 5      | 8      | true
        [[1, 2], [2, 3], [4, 5], [3, 5]]                 | 2      | 4      | true
    }
}

Node를 활용한 코드

public class Node<T extends Comparable<T>> {
    public T value;
    public Node<T> root;

    public Node(T value) {
        this.value = value;
        this.root = this;
    }
}

public class Graph<T extends Comparable<T>> {
    private Map<T, Node<T>> nodeMap = new HashMap<>();

    public void join(T value1, T value2) {
        Node<T> node1 = nodeMap.getOrDefault(value1, new Node<>(value1));
        Node<T> node2 = nodeMap.getOrDefault(value2, new Node<>(value2));

        nodeMap.put(value1, node1);
        nodeMap.put(value2, node2);

        Node<T> root1 = getRoot(node1);
        Node<T> root2 = getRoot(node2);

        // 두 노드의 부모 중 작은 값을 갖는 부모로 들어감
        if (root1.value.compareTo(root2.value) > 0) {
            root1.root = root2.root;
        } else {
            root2.root = root1.root;
        }
    }

    public boolean isSameUnion(T value1, T value2) {
        return getRoot(nodeMap.get(value1)) == getRoot(nodeMap.get(value2));
    }

    private Node<T> getRoot(Node<T> node) {
        if (node.root == node) {
            return node.root;
        }

        return node.root = getRoot(node.root);
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#graphData, #value1, #value2 -> #result"() {
        expect:
        Graph<Integer> graph = new Graph<>()
        graphData.each { values -> graph.join(values.get(0), values.get(1)) }
        graph.isSameUnion(value1, value2) == result

        where:
        graphData                                        | value1 | value2 | result
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 1      | 2      | true
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 2      | 3      | true
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 3      | 5      | false
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 4      | 7      | false
        [[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]] | 5      | 8      | true
        [[1, 2], [2, 3], [4, 5], [3, 5]]                 | 2      | 4      | true
    }
}

참고

• https://m.blog.naver.com/ndb796/221230967614
• https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html