5295. 흘러라 시간! 딴 짓 하기

열 하나를 지우는 행동을 최소화 하여 1,2,3행에 있는 숫자의 구성을 똑같이 만들어야 한다.

이 때 열을 몇개를 지워야 하는지를 출력하는 문제다.

일단 구성을 똑같이 해야하므로 각 줄별로 숫자의 개수를 세어준다.

1행은 1~N까지 무조건 한번씩 나타나고 2~3행은 1~N사이에서 중복 가능하게 랜덤으로 나타난다고 한다.

세어보고 이 개수가 뭘 의미하는지 생각해보자. 일단 각 줄별로 숫자 구성이 동일해야 하므로 열을 지우는 행동을 모두 끝마친 후에는

cnt[0][i] == cnt[1][i] == cnt[2][i]일 것이다. 따라서 cnt[0][i] != cnt[1][i] || cnt[1][i] != cnt[2][i] 라면 손을 봐야 하는 것이다.

만약 cnt가 2 이상이라면 어떤것을 지워야 할지 알 수 없으므로 보류하고 다른 경우를 생각해 보면 명백한 케이스가 있다.

cnt[][i] 에 0이 있는경우. 예제에서 보면 6의 개수가 {1,0,1}로 2열에서는 0이고 나머지에서는 1인 걸 볼 수 있다.

각 행의 숫자 구성이 같아야 하므로 1,3행에서 6을 포함하는 열을 지워야 하는 것을 알 수 있다.

떠올리고 보니 위상정렬과 비슷하고 실제로 그렇게 코딩하니 통과가 떴다.

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
 
struct po {
    int a[3];
};
 
int tc, n, res;
po a[100001];
int ind[100001][3];
 
const bool cmp(const po &a, const po &b) {
    return a.a[0] < b.a[0] ? true : (a.a[0] == b.a[0] ? (a.a[1] < b.a[1] ? true : a.a[1] == b.a[1] ? a.a[2] < b.a[2] : false) : false);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> tc;
 
    for (int t = 1; t <= tc; ++t) {
        memset(ind, 0, sizeof(ind));
        cin >> n;
        res = 0;
        vector<vector<int>> v(n + 1);
        queue<int> q;
        for (int i = 0; i < 3; ++i) for (int j = 1; j <= n; ++j) {
            cin >> a[j].a[i];
            ind[a[j].a[i]][i]++;
            v[a[j].a[i]].push_back(a[j].a[0]);
        }
        sort(a + 1, a + 1 + n, cmp);
        for (int i = 1; i <= n; ++i) 
            for (int j = 1; j < 3; ++j) 
                if (!ind[i][j])
                    q.push(i);
 
        while (q.size()) {
            int x = q.front();
            q.pop();
            if (ind[x][0] == 0) continue;
            for (auto i : v[x]) {
                if (ind[i][0] == 0) continue;
                res++;
                for (int j = 0; j < 3; ++j) {
                    if (ind[a[i].a[j]][j]) {
                        ind[a[i].a[j]][j]--;
                        if (ind[a[i].a[j]][j] == 0)
                            q.push(a[i].a[j]);
                    }
                }
            }
        }
        cout << "#" << t << " " << res << '\n';
    }
    return 0;
}