백준 28251 - 나도리합 (C++)

문제

• 문제 링크

  
   BOJ 28251 - 나도리합 
  

• 문제 요약

나도리의 수 $N$과 쿼리의 수 $Q$가 주어진다.
최초 각 나도리의 크기가 주어지고 $Q$개의 쿼리가 차례로 주어질 때, 그에 맞는 처리를 진행하자.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ N, Q ≤ 200,000$

$0 ≤ s_i ≤ 2,000$

알고리즘 분류

• 자료 구조(data structures)
• 분리 집합(disjoint_set)

풀이

그룹 단위 $merge$연산이 수행된다. 또, 새로운 $merge$가 일어날 때마다 전투력이 전이, 추가된다.
이는 분리 집합을 이용해 간단하고 효율적으로 처리할 수 있다.

전투력을 구하는 정의에 따라, 집합 별 대표 노드를 나타내는 배열 이외에 추가적인 배열을 정의하자.
구체적으로 아래와 같다.

$root[]$ : 그룹 별 대표 노드.

$power[]$ : 그룹 별 총 전투력.

$s[]$ : 그룹 별 총 크기.

전투력을 계산할 때, 두 그룹의 크기의 곱만을 더해주는 것이 아니라 흡수되는 쪽의 $power[]$값도 전이해줘야 함을 유의하자.

자세한 건 아래 코드를 참조하면 되겠다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 200001
using namespace std;
 
ll root[N], power[N], s[N];
 
ll Find(ll x) { return root[x] = root[x] == x ? x : Find(root[x]); }
void Merge(ll x, ll y)
{
    x = Find(x), y = Find(y);
    if (x > y)
    {
        root[x] = y;
 
        power[y] += s[x] * s[y] + power[x];
        s[y] += s[x];
    }
    else if (x < y)
    {
        root[y] = x;
 
        power[x] += s[x] * s[y] + power[y];
        s[x] += s[y];
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    iota(root, root + N, 0);
    ll n, q; cin >> n >> q;
 
    for (ll i(1); i <= n; cin >> s[i++]);
    for (ll i, j; q--;)
    {
        cin >> i >> j;
        Merge(i, j);
        cout << power[Find(i)] << '\n';
    }
}

comment

대회 때 이 문제를 풂으로써 상품에 당첨 되었다! (감사합니다)