어제 시간 복잡도를 계산하지 않아서 시간을 날린 경험을 토대로 오늘은 먼저 가능한지부터 판별했다.
역시나 단순 그래프 탐색으로는 불가능하기 때문에 더 찾아봤고, “서로소 알고리즘” 이라는 것을 알게됐다.

서로소 알고리즘이란

서로소 : 공통 원소가 없는 두 집합

👉 두개의 집합이 공통 원소가 없는 서로소 집합인지를 판별하기 위한 알고리즘이다.

상황

여러개의 집합을 합치는 과정에서, 특정 원소나 집합이 두개가 같은 집합에 속해있는지를 확인해야한다.
즉 서로소 집합이 아닌 것을 확인해야한다.
그래프를 만든 후, 모든 경로를 확인하는 것도 가능하겠지만, 시간 복잡도가 높다.
그럴때 쓰는 것이 서로소 알고리즘

원리

각 집합의 대표 노드를 정한 후 이름표를 붙이듯, 각 원소마다 대표 노드를 저장한다.
어떤 원소 두 개의 대표 노드가 같다면 동일한 집합에 속해 있다. 반대로 다르다면 서로 다른 집합에 속한 서로소 집합인 것이다.

이러기 위해서는 대표노드를 저장하는 규칙이 항상 동일 (대개 더 작은 숫자로)해야한다.

풀이

union 연산

• 서로 연결된 두 노드 A, B의 최종 대표 노드를 확인한다. find 연산 활용 (A’, B’)
  ⭐️ 재귀적으로 찾은 대표 노드를 사용해야함에 유의
• 둘 중 더 작은 대표 노드를 대표 노드로 정한다. (A’라고 가정)
• B’의 대표노드를 A’로 한다.
  ⭐️ B의 대표 노드를 바꾸는 것이 아니라 B’의 대표 노드를 바꾸는 것임에 유의

find 연산 ;

최종 대표 노드( 대표노드와 자신 노드값이 동일함)를 찾을때까지 순회한다.
그러나 최악의 경우 선형 트리가 생성될 수 있다.

개선된 find 연산 :

트리의 구조를 평평하게, 즉 방문한 모든 노드들에 곧바로 최종 대표 노드를 가리키도록 설정한다 (depth를 1로 줄이는 것)

• frind(노드): 어떤 노드의 대표노드를 찾으려고 할때,
  • 해당 노드의 대표 노드가 최종 대표 노드인 경우 :
    • 최종 대표 노드 반환
  • 아닌 경우 :
    • frind(해당 노드의 대표 노드) … 1
      
    • 현재 노드의 대표 노드를 1번의 반환값 (최종 대표 노드 반환) 으로 업데이트
      → 트리의 뎁스가 줄어든다.

1717 집합의 표현

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	130603	43782	26743	29.550%

문제

초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, … , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

예제 입력

7 8 : n, m -> 집합의 개수, 연산 수 
	집합 : 0 1 2 3 4 5 6 7 

0 1 3 : 합치기, 0, 1-3,2,4,5,6,7
1 1 7 : 같이 있는지? no
0 7 6 : 합치기 : 0, 1-3,2,4,5,6-7
1 7 1 : 같이 있는지? no
0 3 7 : 합치기 : 0,1-3-7-6, 2, 4, 5
0 4 2 : 합치기 : 0,1-3-7-6, 4-2, 5
0 1 1 : 합치기 : 0,1-3-7-6, 4-2, 5
1 1 1 : 같이 있는지? yes

예제 출력

NO
NO
YES

그래프 탐색으로 안되는 이유 : 시간 복잡도

그래프 탐색에 걸리는 시간 복잡도 : O(V + E)

• V = 정점(vertex)의 개수
• E = 간선(edge)의 개수

→ 만약 M 모두 확인하는 연산이라면? O(M(N) ⇒ 10^11 : 시간 초과

→ 만약 반반이라면? O(M/2(N+M/2)) ⇒ 50,000 * ( 1050,000) = 10^10 : 시간 초과)

자바 시간 복잡도

지수 표기	대략 시간
100,000	≈ 0.001초 (1ms)
1,000,000 : 1백만 번(10⁶)	≈ 0.01초 (10ms)
10,000,000 : 1천만 번(10⁷)	≈ 0.1초
100,000,000 : 1억 번(10⁸)	≈ 1초
1,000,000,000 : (10^9)	≈ 10초 (보통 시간 초과)

서로소 집합 알고리즘

정답 코드

package day11_GraphDeepening;

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

public class BOJ1717집합의표현_3 {
    static int find(int node, int[] nodes) {
        if (node == nodes[node]) {
            return node;
        }
        nodes[node] = find(nodes[node], nodes);
        return nodes[node];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[m][3];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
        }

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

        for (int i = 0; i < m; i++) {
            int a = arr[i][1];
            int b = arr[i][2];
            if (arr[i][0] == 0) {
                int A = find(a,nodes);
                int B = find(b,nodes);
                int rep = Math.min(A, B);
                int sub = Math.max(A, B);

                nodes[sub] = rep;

            } else {
                if (find(a, nodes) == find(b, nodes)) {
                    sb.append("YES\n");
                } else {
                    sb.append("NO\n");
                }
            }
        }
        System.out.print(sb);
    }
}

실패코드

• union에서 find 로 찾은 최종 대표 노드가 아닌, 단순 대표 노드를 사용해서 틀렸다.

for (int i = 0; i < m; i++) {
            int a = arr[i][1];
            int b = arr[i][2];
            if (arr[i][0] == 0) {
                int rep = Math.min(nodes[a], nodes[b]); // 단순 대표 노드를 사용
                int sub = Math.max(nodes[a], nodes[b]);

                nodes[sub] = rep;

            } else {
                if (find(a, nodes) == find(b, nodes)) {
                    sb.append("YES\n");
                } else {
                    sb.append("NO\n");
                }
            }
        }

반례

4 4
0 3 4
0 1 3
0 2 4
1 1 4

정답

NO

내 출력

YES

마무리

바로 안풀고, 시간 복잡도를 한번 체크한거 칭찬해~