백준 30622 - Rush & Slash (C++)

문제

• 문제 링크

  
   BOJ 30622 - Rush & Slash 
  

• 문제 요약

$2$차원 상의 잡초들의 좌표 $(x_i, y_i)$가 $N$개 주어진다.
일련의 과정을 따라, 모든 잡초들을 제거하기 위해 이동해야 하는 거리의 합의 최솟값을 구해보자.


• 제한

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




$1 ≤ N ≤ 10^5$

$-10^9 ≤ x_i, y_i ≤ 10^9$

주어지는 모든 좌표는 서로 다르다.

알고리즘 분류

• 자료 구조 (data_structures)
• 트리를 사용한 집합과 맵 (tree_set)
• 분리 집합 (disjoint_set)

풀이

모든 좌표 $(x_i, y_i)$에 대해, 해당 좌표를 기준으로 $8$방향을 보며 인접한 좌표가 주어졌는지 확인하자.
$x_i$와 $y_i$의 좌표 범위에 따라 이를 소화할 수 있는 적절한 자료구조를 선택해야 한다.

인접한 좌표들끼리 하나의 컴포넌트를 구성하자.
이는 좌표마다 번호를 부여한 뒤, 분리 집합을 이용해 관리해줄 수 있다.

원점 $(0, 0)$에서 어떤 컴포넌트 $P_i$로 이동하려 할 때, 우리는 이동 거리의 합을 최소화해야 한다.

즉, 집합 $P_i$에 속한 $(x_1, y_1)$, $(x_2, y_2)$, ... , $(x_k, y_k)$ 중 원점과 가장 가까운 좌표로 이동하는 것이 최선이다.

---

이를 모든 컴포넌트들에 대해 수행한 뒤, 각 컴포넌트와의 거리 $dis_1, dis_2, ... , dis_i$ 로 왕복 거리를 누적하자.

마지막 컴포넌트에 다다르면 원점으로 복귀하지 않아도 되므로, $max(dis_1, dis_2, ... , dis_i)$인 컴포넌트를 마지막에 가는 것이 최선이다.

따라서, 누적 거리에서 이를 뺀 값이 최종 답이 되겠다.

전체 코드

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
 
ll dy[]{ -1, 1, 0, 0, -1, -1, 1, 1 };
ll dx[]{ 0, 0, -1, 1, -1, 1, -1, 1 };
 
ll par[100001];
ll find(ll x) { return par[x] ^ x ? find(par[x]) : x; }
void merge(ll x, ll y)
{
    x = find(x), y = find(y);
    x > y ? par[x] = y : par[y] = x;
}
 
int main()
{
    iota(par, par + 100001, 0);
    ll n; cin >> n;
 
    map <pair<ll, ll>, ll> M;
    for (ll i(1); i <= n; i++)
    {
        ll x, y; scanf("%lld %lld", &x, &y);
        for (ll d{}; d < 8; d++)
        {
            ll _x(x + dx[d]), _y(y + dy[d]);
            if (M.count({ _x, _y }))
                merge(i, M[{_x, _y}]);
        }
        M[{x, y}] = i;
    }
 
    unordered_map <ll, ll> P;
    for (auto& [pos, i] : M)
    {
        ll p(find(i)), dis(abs(pos.first) + abs(pos.second));
        if (!P.count(p)) P[p] = dis;
        else P[p] = min(P[p], dis);
    }
 
    ll ans{}, _max{};
    for (auto& [p, dis] : P)
    {
        ans += dis << 1LL;
        _max = max(_max, dis);
    }
 
    cout << ans - _max;
}

comment

끝