Union Find

Union Find는 집합을 다루는 알고리즘으로,
서로소 집합을 효율적으로 다루기 위해 사용한다.

각 집합은 대표자를 가지며,
이 대표자를 이용하여 두 원소가 같은 집합에 속해있는지 여부를 판단할 수 있다.

Union Find는 이름처럼 반드시 두 가지 메서드를 필수적으로 사용하며 하나의 배열을 공유한다.

int unf[] = new int[N + 1];
for (int i = 1 ; i < unf.length ; i++) {
	unf[i] = i;
}

unf 배열은 각 인덱스가 가리키는 대표자 노드를 저장하는 배열로,
union 연산 전에는 각 인덱스의 값 자체를 대표자 노드로 사용하고 있다.

• 1. Union
     두 집합을 합치는 함수
     a가 속한 집합의 대표자 노드와
     b가 속한 집합의 대표자 노드가 다를 경우에만 두 집합을 합친다.

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
  
        // 부모노드가 다를 경우에만 union 연산
        if (a != b) {
            unf[b] = a;
        }
    }

• 2. Find
     v가 속한 집합의 대표자 노드를 찾는 재귀함수
     재귀를 반복하면서 대표자 노드를 찾은 경우에는 대표자 노드를 return,
     대표자 노드가 아닌 경우에는 재귀

    static int find(int v) {
        // 트리노드를 찾을 때 까지 재귀
        if (unf[v] == v) {
            return v;
        } else {
            return unf[v] = find(unf[v]);
        }
    }

[ 백준 ] 여행 가자

이 문제를 예시로,
관계를 다음과 같이 설정하면

    A B C
  
A   0 1 0
B   1 0 1
C   0 1 0

A는 B와 연결되어있고,
B는 A와 C와 연결되어있고,
C는 B와 연결된 것을 확인할 수 있다. ( A - B - C )

위 관계를 바탕으로 Union 연산을 한다면 unf[] 배열은 다음과 같다

unf = { 0 , 1 , 1 , 1 }

모두 연결되어 있으므로 같은 대표자 노드를 가지는 것이다.

1, 2, 3 번째 인덱스를 모두 find 해봤자 모두 같은 대표자 노드 1을 가지므로
예제에 나와있는 0 1 0 , 1 0 1 , 0 1 0 관계는 YES를 출력한다.

-  Java Code

	static int unf[];
    static int find(int v) {

        if (unf[v] == v) {
            return v;
        } else {
            return unf[v] = find(unf[v]);
        }

    }

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

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 도시의 개수
        int N = Integer.parseInt(br.readLine());

        // 여행 계획에 속한 도시들의 수
        int M = Integer.parseInt(br.readLine());

        unf = new int[N + 1];

        // 가장 첫 unf 배열은 각 인덱스로 초기화, 이후 union 연산을 통해 하나의 루트노트로 병합해감
        for (int i = 1; i < unf.length; i++) {
            unf[i] = i;
        }

        // 인접행렬이 1인 값들이 모두 같은 indexRoute 를 가진다면 이어진 것, 여행 가능
        int Graph[][] = new int[N + 1][N + 1];

        // 그래프 그리기
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                Graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // union
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (Graph[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        
        // 루트노드를 index로 설정
        int index = find(Integer.parseInt(st.nextToken()));

        // 이후에 올 인덱스의 루트노드가 하나라도 다를 경우 NO 출력
        for (int i = 1; i < M; i++) {
            if (index != find(Integer.parseInt(st.nextToken()))) {
                System.out.println("NO");
                System.exit(0);
            }
        }

        System.out.println("YES");

    }