유니온 파인드

• 유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

집합 표현하기

Question

Code

import java.util.Scanner;

public class N50_P1717_집합_표현하기 {

    public static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        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();
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (question == 0) {
                union(a, b);
            } else {
                if (checkSame(a, b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }


    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    public static int find(int a) {
        if (a == parent[a])
            return a;
        else
            return parent[a] = find(parent[a]);
    }

    public static boolean checkSame(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return true;
        }
        return false;
    }
}

Idea

reference

여행 계획 짜기

Question - 1976

Code

import java.util.Scanner;

public class N51_P1976_여행_계획짜기 {
    static int city;
    static int road;
    public static int[] parent;

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

        city = sc.nextInt();
        road = sc.nextInt();

        int[][] map = new int[city + 1][city + 1];

        for (int i = 1; i <= city; i++) {
            for (int j = 1; j<= city; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        int[] route = new int[road + 1];
        for (int i = 1; i <= road; i++) {
            route[i] = sc.nextInt();
        }

        parent = new int[city + 1];
        for (int i = 1; i <= city; i++) {
            parent[i] = i;
        }

        for (int i =1; i <= city; i++) {
            for (int j = 1; j <= city; j++) {
                if (map[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        // 여행 계획 도시들이 1개의 대표 도시로 연결되어 있는지 확
        int index = find(route[1]);
        for ( int i =2; i < route.length; i++) {
            if (index != find(route[i])) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }
    public static int find(int a) {
        if (a == parent[a])
            return a;
        else {
            return parent[a] = find(parent[a]);
        }
    }
}

Idea

• 그래프 이론

• 자료 구조

• 그래프 탐색

• 분리 집합

reference

거짓말쟁기가 되긴 싫어

Question - 1043

Code

import java.util.ArrayList;
import java.util.Scanner;

public class N52_P1043_거짓말쟁이가_되긴_싫어 {

    public static int[] parent;
    public static int[] avoidInfo;
    public static ArrayList<Integer>[] partyInfo;
    public static int result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int peopleTotal = sc.nextInt();
        int partyNum = sc.nextInt();
        int avoidNum = sc.nextInt();
        result = 0;

        avoidInfo = new int[avoidNum];
        for (int i = 0; i < avoidNum; i++) {
            avoidInfo[i] = sc.nextInt();
        }

        partyInfo = new ArrayList[partyNum];
        for (int i = 0; i < partyNum; i++) {
            partyInfo[i] = new ArrayList<Integer>();
            int participate = sc.nextInt();
            for (int j = 0; j < participate; j++) {
                partyInfo[i].add(sc.nextInt());
            }
        }

        parent = new int[peopleTotal + 1];
        for (int i = 0; i <= peopleTotal; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < partyNum; i++) {
            int firstPeople = partyInfo[i].get(0);
            for (int j = 1; j < partyInfo[i].size(); j++) {
                union(firstPeople, partyInfo[i].get(j));
            }
        }

        for (int i = 0; i < partyNum; i++) {
            boolean isPossible = true;
            int cur = partyInfo[i].get(0);
            for (int j = 0; j < avoidInfo.length; j++) {
                if (find(cur) == find(avoidInfo[j])) {
                    isPossible = false;
                    break;
                }
            }
            if (isPossible)
                result++;
        }
        System.out.println(result);
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    // sss
    public static int find(int a) {
        if (a == parent[a]) {
            return a;
        } else {
            return parent[a] = find(parent[a]);
        }
    }
}

Idea

reference