BOJ 31886 : Gridev's Protocol

• 문제 링크 : boj.kr/31886
• 난이도 : P5
• 태그 : 시뮬레이션

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    vector<unordered_set<int>> r1(n+1), c1(n+1);
    vector<pii> arr;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        r1[a].insert(b);
        c1[b].insert(a);
        arr.emplace_back(pii(a,b));
    }

    int ans = INF;
    //rcrcrc
    queue<pii> _q; // r=0, c=1 & num
    for(int i = 1; i <= n; i++) {
        if(r1[i].size() <= k) {
            _q.push(pii(0, i));
        }
    }
    for(int i = 1; i <= n; i++) {
        if(c1[i].size() <= k) {
            _q.push(pii(1, i));
        }
    }
    int removed = 0;
    int cnt = 0;
    int before = -1;
    while(!_q.empty()) {
        pii f = _q.front(); _q.pop();
        if(f.first == 0 && r1[f.second].size() == 0) continue;
        if(f.first == 1 && c1[f.second].size() == 0) continue;
        if(f.first != before) {
            cnt++;
            before = f.first;
        }
        if(f.first == 0) {
            for(auto u : r1[f.second]) {
                c1[u].erase(f.second);
                removed++;
                if(c1[u].size() <= k) {
                    _q.push(pii(1, u));
                }
            }
            r1[f.second].clear();
        }
        if(f.first == 1) {
            for(auto u : c1[f.second]) {
                r1[u].erase(f.second);
                removed++;
                if(r1[u].size() <= k) {
                    _q.push(pii(0, u));
                }
            }
            c1[f.second].clear();
        }
    }
    if(removed == m) {
        ans = min(ans,cnt);
    }

    //crcrcr
    vector<unordered_set<int>> r2(n+1), c2(n+1);
    for(int i = 0; i < m; i++) {
        int a = arr[i].first;
        int b = arr[i].second;
        r2[a].insert(b);
        c2[b].insert(a);
    }
    while(!_q.empty()) _q.pop();
    before = -1;
    for(int i = 1; i <= n; i++) {
        if(c2[i].size() <= k) {
            _q.push(pii(1, i));
        }
    }
    for(int i = 1; i <= n; i++) {
        if(r2[i].size() <= k) {
            _q.push(pii(0, i));
        }
    }
    removed = 0;
    cnt = 0;
    while(!_q.empty()) {
        pii f = _q.front(); _q.pop();
        if(f.first == 0 && r2[f.second].size() == 0) continue;
        if(f.first == 1 && c2[f.second].size() == 0) continue;
        if(f.first != before) {
            cnt++;
            before = f.first;
        }
        if(f.first == 0) {
            for(auto u : r2[f.second]) {
                c2[u].erase(f.second);
                removed++;
                if(c2[u].size() <= k) {
                    _q.push(pii(1, u));
                }
            }
            r2[f.second].clear();
        }
        if(f.first == 1) {
            for(auto u : c2[f.second]) {
                r2[u].erase(f.second);
                removed++;
                if(r2[u].size() <= k) {
                    _q.push(pii(0, u));
                }
            }
            c2[f.second].clear();
        }
    }
    if(removed == m) {
        ans = min(ans,cnt);
    }
    cout << (ans != INF ? ans : -1);
    return 0;
}

---

풀이

한 행동을 두 번 연속으로 하는 것은 비효율적이라는 것을 알 수 있다. 두 번째 행동은 아무런 변화도 일으키기 못하기 때문이다. 따라서 두 행동을 번갈아 해야 하고, 그러면 답이 될 수 있는 경우는 1번 행동부터 시작한 경우, 2번 행동부터 시작한 경우이다. 단 행동을 할때마다 어떤 줄이 지워지는지 탐색하면 시간 초과가 발생하므로, 한 행동이 끝난 후 다음 행동시에 영향을 받는 줄을 저장해주어야 한다.