[백준 32070번] 색깔 모으기

문제 링크

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

 

문제 요약

같은 색깔의 공을 하나의 상자에 모으는 데 필요한 최소 이동 횟수를 구하는 문제이다. 각 상자는 최대 두 개의 공을 담을 수 있다. 공을 꺼낼 때는 상자의 위에 있는 공만 꺼낼 수 있으며, 공을 넣을 때는 빈 상자나 같은 색깔의 공이 있는 상자에만 넣을 수 있다.

 

문제 풀이

같은 색깔의 공을 하나의 상자에 모으기 위해 공을 옮기다 보면 연쇄적으로 다른 공들도 움직여야 하는 상황이 발생한다. 이 과정에서 연쇄적으로 움직이는 공들을 추적하다 보면 하나 이상의 싸이클이 만들어지는 것을 발견할 수 있다.

두 개의 싸이클이 생긴 예제

위 예시를 보면 1, 2, 3, 4번 공의 싸이클과 5, 6, 7번 공의 사이클은 답을 구하는 과정에서 서로 영향을 끼치지 않는다.

 

싸이클사이클 내에 있는 공들을 같은 색끼리 모으기 위해 필요한 최소 이동 횟수는 정해져 있다. 먼저 사이클에 있는 공 한 개를 빈 상자로 옮겨 빈틈(?)을 만들어야 한다. 그런 다음, 그 빈틈을 이용해 나머지 공들을 하나씩 옮기며 색을 맞춘다. 이 과정에서 필요한 이동 횟수를 계산해 보면, 사이클에 속한 상자의 개수가 \(x\) 개일 때, \(x + 1\) 번이 된다.

 

그러나 모든 싸이클에서 이 방법이 적용 가능한 것은 아니다. 사이클 내에서 상자 위에 올라와 있는 색의 쌍이 두 쌍 이상이면 공을 연쇄적으로 움직이지 못해 답을 구할 수 없다. 이러한 경우에는 문제에서 요구한 대로 -1을 출력하면 된다.

 

소스 코드

실제로 공을 옮기는 시뮬레이션이 필요한 것이 아니라 싸이클사이클 내에 속한 상자의 개수만 알면 되기 때문에 사이클을 관리하는 것은 유니온 파인드 자료구조를 사용하는 것이 좋다. 다음은 이 문제를 풀기 위한 전체 코드이다.

 

#include <stdio.h>
#include <vector>

using namespace std;

int n, top_pairs[200010];
bool solved[200010];
vector<int> ball_idx[200010];

// 유니온 파인드 클래스 정의
class UnionFind {
    vector<int> parent, rank, cnt;
    
public:
    UnionFind(int sz): parent(sz), rank(sz, 1), cnt(sz, 1) {
        for (int i = 0 ; i < sz ; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int u) {
        if (u == parent[u]) {
            return u;
        }
        
        return parent[u] = find(parent[u]);
    }
    
    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        
        if (u == v) {
            return;
        }
        
        if (rank[u] > rank[v]) {
            swap(u, v);
        }
        
        parent[u] = v;
        cnt[v] += cnt[u];
        
        if (rank[u] == rank[v]) {
            ++rank[v];
        }
    }
    
    int getCnt(int u) {
        u = find(u);
        
        return cnt[u];
    }
};

int main() {
    scanf("%d", &n);
    
    // 각 공의 위치를 저장
    // 짝수는 상자의 윗부분, 홀수는 상자의 아랫부분에 있다는 것을 의미
    for (int i = 1 ; i <= n ; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        ball_idx[a].push_back(i * 2);
        ball_idx[b].push_back(i * 2 + 1);
    }
    
    UnionFind uf(n + 1);
    
    // 같은 색 공이 있는 상자들끼리 싸이클을 만든다
    for (int i = 1 ; i <= n ; ++i) {
        uf.merge(ball_idx[i][0] / 2, ball_idx[i][1] / 2);
    }
    
    // 싸이클 내에서 상자 위에 올라와 있는 색의 쌍이 두 쌍 이상인지 확인
    for (int i = 1 ; i <= n ; ++i) {
        if (ball_idx[i][0] % 2 == 0 && ball_idx[i][1] % 2 == 0) {
            int rootIdx = uf.find(ball_idx[i][0] / 2);
            
            top_pairs[rootIdx] += 1;
        }
    }
    
    for (int i = 1 ; i <= n ; ++i) {
        int rootIdx = uf.find(ball_idx[i][0] / 2);
        
        if (top_pairs[rootIdx] >= 2) {
            puts("-1");
            
            return 0;
        }
    }
    
    int ans = 0;
    
    // 각 싸이클에 대해 최적해를 계산
    // 싸이클에 속한 상자의 갯수가 한 개라면 이미 같은 색이라는 것을 의미하므로 계산하지 않는다
    for (int i = 1 ; i <= n ; ++i) {
        int rootIdx = uf.find(ball_idx[i][0] / 2);
        
        if (solved[rootIdx]) {
            continue;
        }
        
        solved[rootIdx] = true;
        
        int x = uf.getCnt(rootIdx);
        
        if (x >= 2) {
            ans += x + 1;
        }
    }
    
    printf("%d\n", ans);
}