[BOJ] 1717 - 집합의 표현

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

난이도

유니온파인드 / ⭐️⭐️⭐️

 

문제풀이 

유니온 파인드 문제이다. 하지만 유니온파인드로 풀었으나 계속 시간 초과가 났다.

 

유니온 파인드란, 한마디로 특정 원소가 어떤 유니온(집합)에 포함되어있는지 찾는 알고리즘이다. 서로소집합(disjoint-set) 이라고도 한다. 특정 원소가 여러 집합에 포함되지 않고 하나의 집합에만 포함되기 때문이다. 

최적화를 위해서는 최상위 부모를 찾은뒤, 재귀에서 나오면서 지나쳐온 모든 노드들에 최상위 부모 정보를 넣어주어야한다.

 

개인적인 상상으로는 조직도와 관련된 문제에서 활용될 수 있을 것 같다. 같은 팀장 아래있는 직원인지 확인하기 등/..

 

유니온 파인드 로직

1) 나 자신을 부모로 갖도록 배열 생성

2) 재귀를 통해 나의 최상위 부모를 찾는 find() 함수 구현 (return 부분 주의)

3) 두 집합을 합치는 union() 함수 구현

3-1) 앞 단계에서 만든 find()함수를 이용해 두 집합의 최상위 부모 찾기

3-2) 하나의 최상위 부모가 나머지 최상위 부모를 갖도록 대입연산

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int arr[1000001];

int find(int n)
{
    if (arr[n] == n)
    {
        return n;
    }
    else
    {
        return arr[n] = find(arr[n]); //check point 1) 
    }
}

void unionn(int a, int b)
{
    int p1 = find(a);
    int p2 = find(b);

    if (p1 != p2)
    {
        arr[p1] = p2;
    }
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
    {
        arr[i] = i;
    }

    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        if (a == 0)
        {
            unionn(b, c);
        }
        else if (a == 1)
        {
            if (find(b) == find(c))
            {
                cout << "YES\n"; // checkpoint 2)
            }
            else
            {
                cout << "NO\n"; // checkpoint 2)
            }
        }
    }
}

 

주의할점

핵심은 checkpoint 1)  부분이다. dfs를 나오면서 같은트리의 노드들이 최상위 부모를 가지도록 갱신해준다. 

하지만 이를 고친후에도 계속하여 시간초과가 났다. 심지어 인터넷에서 코드를 찾아서 내코드와 비교해도 다를점이 없어보였다.

최적화를 위해 union시 작은 트리를 큰 트리에 붙여주는 코드도 추가해봤지만  여전히 시간 초과가 났다. (각 노드가 자신의 부모정보를 가지는게 아니라 최상위 부모값만 가지기 때문에 이 문제랑은  상관없을 것 같다.)

문제는 의외로 checkpoint 2) 로 표시해둔 endl; 부분이었다.

 

endl; 이 시간이 오래걸리기때문에 아래 코드를 추가해도 시간초과가 난다고 한다. 

ios_base::sync_with_stdio(false);
cin.tie(0);

printf를 쓰거나 endl을 지우고 \n을  추가하니 시간초과가 바로 해결되었다. 

printf("%s","YES\n");
또는
cout << "YES" << "\n";
cout << "YES\n" ;