[이코테] 그래프 이론 - 팀 결성 - JAVA

최영환·2022년 11월 16일

이코테

목록 보기

22/24

💡 문제

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1 개의 팀이 존재한다. 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용할 수 있다.

'팀 합치기' 연산은 두 팀을 합치는 연산이다.
'같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.

선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인'연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 <= N, M <= 100,000)
다음 M개의 줄에는 각각의 연산이 주어진다.
'팀 합치기' 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다.
'같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산이다.
a와 b는 N 이하의 양의 정수이다.

출력

'같은 팀 여부 확인'연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.

💬 입출력 예시

입력

출력

NO
NO
YES

📌 풀이(소스코드)

import java.util.Scanner;

// 팀 결성
public class Graph_01 {
    // 노드의 개수 n, 간선의 개수 m
    public static int n, m;
    public static int[] parent = new int[100001];

    // Find 연산
    public static int findParent(int x) {
        // 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = findParent(parent[x]);
    }

    // Unino 연산
    public static void unionParent(int a, int b) {
        // 루트 노드를 찾음
        a = findParent(a);
        b = findParent(b);
        // 둘 중 작은 값을 부모 노드로 설정
        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        // 부모 테이블 초기화(자기 자신)
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < m; i++) {
            int oper = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();

            // Union 연산 수행
            if (oper == 0) {
                unionParent(a, b);
            }
            // Find 연산 수행 후 결과 출력
            else {
                if (findParent(a) == findParent(b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
        sc.close();
    }
}