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 처럼 해결했다.
실제 코드
나머지 주의 할 점은 코드에 주석으로 처리했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#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;
}