[백준/Java] 1717번 집합의 표현

-Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1717 {
    static int[] nodes;
    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int nodeNum = Integer.parseInt(st.nextToken());
        int testCase = Integer.parseInt(st.nextToken());
        // 노드 초기화
        nodes = new int[nodeNum + 1];
        for (int i = 1; i <= nodeNum; i++) {
            nodes[i] = i;
        }
        // 입력 받기
        for (int t = 0; t < testCase; t++) {
            st = new StringTokenizer(br.readLine());
            int calc = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            if (calc == 0) {
                union(start, end);
            } else {
                System.out.println(isSame(start, end) ? "YES" : "NO");
            }
        }

    }
    // 유니온 파인드 로직
    private static void union(int start, int end) {
        start = find(start);
        end = find(end);
        nodes[end] = start;
    }
    private static int find(int node) {
        // 자기 자신과 대표 노드가 같은 경우 반환
        if (nodes[node] == node) return node;
        // 다른 경우 대표 노드 찾기 및 빠져 나오면서 값 변경
        return nodes[node] = find(nodes[node]);
    }
    // 두 노드가 같은 집합인지 확인
    private static boolean isSame(int node1, int node2) {
        return find(nodes[node1]) == find(nodes[node2]);
    }
}

강의에서 유니온 파인드에 대해서 듣고 풀어봤습니다.

일단 처음에 union시 find한 값을 가지고 값을 변경해야 하는데 end만 find하고 값을 넣었었고 이후 find시 자기가 대표 노드가 아닌 경우 값을 변경하고 넘어가는 부분에서 좀 헤매었습니다.

또한 같은 노드인지 확인을 처음에 nodes[start] == nodes[end]로 확인하고 출력을 했으나 예제 입력과 다른 입력에서 오류가 남을 확인 하고 문제를 찾아보니 find시 값을 변경한다고 해도 경로 압축 등을 통해서 배열이 바뀔 수 있어 한 번 더 해서 비교해야 정확한 값을 반환한다는 것을 알고 해결했습니다. 처음 접한 알고리즘과 문제라 다음에 다시 한번 해결해 봐야겠습니다.