[BAE/<JOON> 문제풀이] 16367. TV Show Game

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

16367번: TV Show Game

서론

SCC 단원 마지막 문제였다. 딱히 특별하진 않았던 것 같다. SCC도 그래프다 보니까 직관적이여서 다른 분류들에 비해 좀 쉬운 것 같다.

---

풀이

객원들이 예측한 3가지 색 중 2가지 이상이 맞아야 하므로 만약 3가지 색 중 하나가 틀린다면 나머지 2개는 반드시 맞아야하는 강제성이 생긴다. 이 점을 이용해 그래프를 생성할 수 있다.

문제의 예제 입력 1번을 예로 들면

7 5
3 R 5 R 6 B
1 B 2 B 3 R
4 R 5 B 6 B
5 R 6 B 7 B
1 R 2 R 4 R

 

첫 번째 방청객은 3 5 6 번 램프에 대해 각각 빨강 빨강 파랑을 예측했다.

즉, 3번 램프가 빨강이 아닐 경우, 5번과 6번 램프는 반드시 빨강과 파랑이어야 한다.

마찬가지로 5번 램프가 빨강이 아닐 경우, 3번과 6번 램프는 반드시 빨강과 파랑이어야 한다.

마지막으로 6번 램프가 파랑이 아닐 경우, 3번과 5번 램프는 반드시 모두 빨강이어야 한다.

 

이런 식으로 모든 방청객들의 예측을 모아 그래프를 형성할 수 있다.

( 두 색에도 true / false를 부여해서 코드를 작성하면 편리하다. ) 

 

이 후, 그래프에 대해 SCC를 형성하고 사이클 내에 같은 정점의 true / false 항목이 동시에 있는지 확인 후

위상 정렬 역순으로 순회하며 false를 대입하면 주어진 2-SAT를 만족하는 경우를 구할 수 있다.

---

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
using ll = long long;
int k, n;
vector<vector<int>> arr, scc;
vector<int> vis, is, pos, sn;
stack<int> st;
struct sccnode {
    int si, i;
};
bool cmp(sccnode a, sccnode b) {
    return a.si > b.si;
}
int cnt = 0;
int getp(int x) {
    return x < 0 ? -x + k : x;
}
int r(int x) {
    pos[x] = cnt++;
    st.push(x);
    vis[x] = 1; 
    int mp = pos[x];
    for (auto nx : arr[x]) {
        if (vis[nx] == 0) {
            int ret = r(nx);
            mp = mp < ret ? mp : ret;
        }
        else if (is[nx] == 0) {
            mp = mp < pos[nx] ? mp : pos[nx];
        }
    }    
    if (mp == pos[x]) { // 내가 방문 순서가 제일 작은 경우 내 위로 전부 scc 다                
        vector<int> sl;
        while (!st.empty() && st.top() != x) {            
            sl.push_back(st.top()); is[st.top()] = 1; sn[st.top()] = scc.size();             
            st.pop();
        }
        sl.push_back(st.top()); is[st.top()] = 1; sn[st.top()] = scc.size(); 
        st.pop();
        scc.push_back(sl);
    }
    return pos[x] = mp; // 가장 작은 정점 번호 리턴하기 
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> k >> n;
    vis = is = pos = sn = vector<int>(k * 2 + 1);
    arr = vector<vector<int>>(k * 2 + 1);
    for (int i = 1; i <= n; i++) {
        vector<int> p1, p2;
        for (int j = 1; j <= 3; j++) {
            int kn; char kc; cin >> kn >> kc; p1.push_back(kn);            
            p2.push_back(kc == 'R' ? 1 : -1);
        }
        for (int j = 1; j <= 3; j++) {
            for (int l = 1; l <= 3; l++) {
                if (j == l) continue;
                arr[getp(p1[j - 1] * p2[j - 1] * -1)].push_back(getp(p1[l - 1] * p2[l - 1])); // 현재 번호가 틀리다면 나머지 두개는 무조건 맞아야 함
            }
        }
    }
    for (int i = 1; i <= k * 2; i++) {
        if (vis[i] == 1) continue;
        r(i);
    }
    for (int i = 1; i <= k; i++) {
        if (sn[i] == sn[i + k]) {
            cout << -1;
            return 0;
        }
    }
    vector<int> res(k * 2 + 1, -1);
    vector<sccnode> sp;
    for (int i = 1; i <= k * 2; i++) {
        sp.push_back({ sn[i], i });
    }
    sort(sp.begin(), sp.end(), cmp);
    for (auto s : sp) {
        int pn = s.i - (s.i > k ? k : 0);
        if (res[pn] == -1) {
            res[pn] = (s.i > k ? 1 : 0); // 뒤부터 false 적용
        }
    }
    for (int i = 1; i <= k; i++) {
        cout << (res[i] == 1 ? 'R' : 'B');
    }
    return 0;
}