BAEKJOON 16367번: TV Show Game

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

16367번: TV Show Game

관찰

해당 문제에서는 사람들의 추론 결과를 이용하여 모두가 3개 중 2개 이상의 색을 맞출 수 있는지 확인하라고 하고 있다.

이는 곧 2개 이상 틀리면 안 된다는 것과 같다. 이를 식으로 표현해 보자. 색깔을 맞출 램프를 편의상 A, B, C라 하겠다.

 

f = ( "A 맞춤" or "B 맞춤") and ( "B 맞춤" or "C 맞춤") and ( "C 맞춤" or "A 맞춤")

 

풀이

위 식은 2-SAT 문제의 형태를 띤다.

램프의 색은 두 가지 이므로, Red를 true, Blue를 false로 잡고, 논리식을 새운 후 SCC를 통해 해를 구해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
vector<vi>G,GT,SCC;
vector<bool>vis;
stack<int>f;
vi cn;
bool T;
int N,M;
void DFS(int x){
    vi g=(T)?GT[x]:G[x];
    for(int y:g){
        if(vis[y])continue;
        vis[y]=true;
        if(T){
            SCC.back().push_back(y);
            cn[y]=SCC.size();
        }
        DFS(y);
    }
    if(!T)f.push(x);
}
int FALSE(int x){
    return x<=N?x+N:x-N;
}
void make_edge(int u,int v){
    G[FALSE(u)].push_back(v);
    GT[v].push_back(FALSE(u));
    G[FALSE(v)].push_back(u);
    GT[u].push_back(FALSE(v));
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin>>N>>M;
    G.resize(2*N+1);GT.resize(2*N+1);
    cn=vi(2*N+1,0);
    T=false;
    for(int i=0;i<M;i++){
        int A,B,C;char a,b,c;cin>>A>>a>>B>>b>>C>>c;
        if(a=='B')A=N+A;
        if(b=='B')B=N+B;
        if(c=='B')C=N+C;
        make_edge(A,B);
        make_edge(B,C);
        make_edge(C,A);
    }
    vis=vector<bool>(2*N+1,false);
    for(int x=1;x<=2*N;x++){
        if(vis[x])continue;
        vis[x]=true;
        DFS(x);
    }
    T=true;
    vis=vector<bool>(2*N+1,false);
    while(!f.empty()){
        int x=f.top();f.pop();
        if(vis[x])continue;
        vis[x]=true;
        SCC.push_back({x});
        cn[x]=SCC.size();
        DFS(x);
    }
    bool ans=true;
    for(int i=1;i<=N;i++)ans&=(cn[i]!=cn[i+N]);
    if(!ans){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=N;i++)cout<<(cn[i]>cn[i+N]?'R':'B');
    return 0;
}