2-SAT

백준 16367번 TV Show Game 문제풀이

[16367 TV Show Game] https://www.acmicpc.net/problem/16367 .
문제를 2-SAT문제로 변환해서 풀자!

2-SAT를 이용해서 여러 논리 관계들이 모순이 있는 지 없는지 알 수 있다.

문제상황 파악하기.

참가자들이 각각 3개의 추측을 낼 수 있고, 그 중 2개가 맞아야한다.
모든 사람들이 2개 이상 맞을 수 없다면 -1, 그럴 수 있다면 그렇게 만드는 전구 배치를 생각해내자!

2-SAT가 뭐길래?

2-Satisfiability로 충족가능성 문제이다.
2개의 항으로 이루어진 절 : (A+B) -> 요건 부울대수
그 절들의 논리곱으로 이루어진 식의 해를 구할 수 있다.
예를 들면, (A+B)(C+~A)(~D+B)가 참이 가능하도록 만드는 값을 구할 수 있는 것이다.
이때 , (A+B)를 그래프의 간선으로 ~A -> B, ~B -> A로 나타낼 수 있다.
A가 거짓이면 B는 참이어야하고, B가 거짓이면 A는 참이어야하기 때문이다.
그래프의 SCC를 구해서 A와 ~A가 같은 SCC에 있다면 이것은 모순이다.
그리고 A가 위상정렬 상 앞에 있다면 A -> ~A꼴이므로 ~A가 참이고,
위상정렬 상 뒤에 있다면 ~A -> A꼴이므로 A가 참이다.

아이디어 얻기.

가장 중요한 아이디어는 3개중 2개 이상을 성공한다는 것은 아무거나 2개를 고르면 그 중 하나는 성공한다는 뜻이다.
이를 이용하여 참가자가 각각 고른 3개의 선택 중 2개를 고른것이 무조건 참이다를 해결하면 된다.
R이나 B중 하나를 참이라고 생각하고 해결해야하므로 그래프의 정점은 최대 10000개가 된다.

주의할 점

2-SAT문제를 풀 때 주의점은 정리를 잘해서 간선이 하나라도 이상하게 된것이 없는지 잘 봐야한다.
그리고 참과 거짓 둘다 나타낼 때 음수로 나타낼 수가 없어서 별도의 연산으로 공간을 만들어야하는데 그 때 OutOfBounds나 중복으로 접근하게 되는 것을 주의하자.
나는 모든 2-SAT문제를 풀때 1의 역은 1+k, 2의 역은 2+k 처럼 해결했다.

실제 코드

나머지 주의 할 점은 코드에 주석으로 처리했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX = 10001;
int k, n;
vector<int> G[MAX], R[MAX], C, order;

void DFS1(int here){
    C[here] = -1;
    for(int next : G[here]){
        if(!C[next]) DFS1(next);
    }
    order.push_back(here);
}

void DFS2(int here, int color){
    C[here] = color;
    for(int next : R[here]){
        if(C[next]==-1) DFS2(next, color);
    }
}

void SCC(){
    C = vector<int> (2*k+1, 0);
    for(int i=1;i<=2*k;i++) if(!C[i]) DFS1(i);
    reverse(order.begin(), order.end());
    int cnt = 0;
    for(int i : order) if(C[i]==-1) DFS2(i, ++cnt);
}

int main(){
    fast_io;
    cin >> k >> n;
    int l[3]; char c[3];
    int notl[3];
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            cin >> l[j] >> c[j];
            notl[j] = l[j]+k;
            if(c[j]=='R'){
                l[j] += k;
                notl[j] = l[j]-k;
            }
        }
        // 0&1
        G[notl[0]].push_back(l[1]);
        R[l[1]].push_back(notl[0]);
        G[notl[1]].push_back(l[0]);
        R[l[0]].push_back(notl[1]);
        // 1&2
        G[notl[1]].push_back(l[2]);
        R[l[2]].push_back(notl[1]);
        G[notl[2]].push_back(l[1]);
        R[l[1]].push_back(notl[2]);
        // 0&2
        G[notl[0]].push_back(l[2]);
        R[l[2]].push_back(notl[0]);
        G[notl[2]].push_back(l[0]);
        R[l[0]].push_back(notl[2]);
    }
    SCC();
    
    bool ok = true;
    for(int i=1;i<=k;i++){
        if(C[i]==C[i+k]) ok = false;
    }
    
    if(ok){
        for(int i=1;i<=k;i++){
            if(C[i]>C[i+k]) cout << 'B';
            else cout << 'R';
        }
    }else cout << -1;
}

2-SAT

백준 16367번 TV Show Game 문제풀이

문제상황 파악하기.

2-SAT가 뭐길래?

아이디어 얻기.

주의할 점

실제 코드

Leave a comment

2024

2023

2022