[코딩테스트] 백준 1717 자바

백준 1717

백준 1717 문제

해당 문제는 합집합 연산과 두 원소가 같은 집합에 포함되는지 확인하는 연산을 수행하라는 문제인데 두 원소가 같은 집합에 있는지 확인하는 알고리즘인 유니온 파인드를 사용하면 풀 수 있다.

import java.util.*;

public class Boj1717 {

    private static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 노드의 개수 -1
        int m = sc.nextInt(); // 질의의 개수
        parent = new int[n + 1]; // 대표 배열 선언

        // 대표 노드 초기화
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }

        // 질의 계산
        for (int i = 0; i < m; i++) {
            int question = sc.nextInt(); // 질의의 종류 0 or 1
            int a = sc.nextInt(); // 첫 번째 노드
            int b = sc.nextInt(); // 두 번째 노드

            if (question == 0) {
                union(a, b); // 첫 번째 노드와 두 번째 노드를 연결
            } else { // 두 원소가 같은 집합인지 확인
                if (find(a) == find(b)) { // union 연산을 통해 경로 압축을 하였기 때문에 같은 집합이라면 두 노드의 대표 노드가 같아야 한다.
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    // 주어진 두 노드를 연결 (합집합 연산)
    private static void union(int a, int b) {
        a = find(a); // 첫 번째 노드의 대표 노드
        b = find(b); // 두 번째 노드의 대표 노드
        if (a != b) { // 두 대표 노드가 다르다면 (같은 집합이 아니라면)
            parent[b] = a; // 두 번째 노드의 대표 노드의 대표 노드를 첫 번째 노드의 대표 노드로 변경
        }
    }

    // 대표 노드를 찾는다.
    private static int find(int a) {
        if (parent[a] == a) { // 노드의 인덱스와 값이 같으면
            return a; // 해당 노드가 대표 노드이기 때문에 해당 노드를 그대로 반환
        }
        // 노드의 인덱스와 값이 다르면 해당 노드는 대표 노드가 아니기 때문에
        parent[a] = find(parent[a]); // 재귀 호출을 통해 대표 노드를 찾고, 해당 노드의 대표 노드를 찾은 대표 노드로 변경
        return parent[a]; // 찾은 대표 노드를 반환
    }
}

풀이

1. 노드의 개수와 질의의 개수를 각각 n과 m으로 입력 받는다.
2. n+1만큼 대표 배열 parent를 선언하고 각 인덱스로 값을 초기화해준다.
3. 질의의 개수 m만큼 반복하며 질의의 종류 question과 첫 번째 노드(원소) a와 두 번째 노드(원소) b를 입력 받는다.
4. find() 메서드는 매개변수를 통해 들어온 인자 노드의 인덱스와 값이 같은지 확인하고, 같으면 그 노드가 대표 노드이기 때문에 해당 노드를 반환한다.
   인자 노드의 인덱스와 값이 다르면 해당 노드는 대표 노드가 아니기 때문에 find() 메서드를 재귀 호출하여 대표 노드를 찾고, 찾은 대표 노드를 자신의 대표 노드로 업데이트 해준다.
5. union() 메서드는 입력된 a 노드와 b 노드의 대표 노드를 find() 메서드를 통해 구한 다음에 a와 b의 값을 각각의 대표 노드로 업데이트를 하고, 두 대표 노드가 다르면 b의 대표 노드의 값을 a 노드의 대표 노드로 변경해준다.
6. question이 0이면 union(a, b) 메서드를 호출하여 합집합 연산을 한다.
7. question이 1이면 find(a)와 find(b)를 호출하여 두 노드의 대표 노드가 같은 지 확인한다.