[백준 16367] TV Show Game

문제 링크 => 16367번: TV Show Game (acmicpc.net)

16367번: TV Show Game

---

SCC 를 활용한 2-SAT 문제이다.

 

이 문제는 3개중에 2개를 만족하도록 세워야 하는게 핵심이다.

 

a, b, c가 존재할 때, a, b가 true 이거나 a, c가 true 이거나 b, c가 true 임을 보이면 된다.

 

즉, (a v b)^(b v c)^(c v a) 이면 a, b, c 셋 중에 하나가 false라고 하더라도 항상 true가 나온다.

 

따라서 (~a -> b)^(~b -> c)^(~c -> a) 를 만족하도록 연결해주면 끝이다.

 

문제 풀다가 막혔던 점 => ~a -> b 뿐만 아니라 ~b -> a 대우 또한 연결해줘야 한다. 대우를 연결해주는것을 잊지 말자.

 

또한 Kosaraju's Algorithm 과 Tarjan's Algorithm 으로 매겨진 inDegree 에 대하여 비교 방법이 다르다는 것 다음과 같이 알아두도록 하자

 

(1) Kosaraju's Algorithm 적용시 => inDegree[i] < inDegree[~i] 일때 false, 그 반대는 true

(2) Tarjan's Algorithm 적용시 => inDegree[i] < inDegree[~i] 일때 true, 그 반대는 false

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M, node_num, scc_Level;
int low[10001], dfn[10001], inDegree[10001];
vector<int> v[10001];
stack<int> s;
bool visited[10001];

int notX(int x) {
	if (x > N) return x - N;
	return x + N;
}

void input() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int x1, x2, x3;
		char c1, c2, c3;

		cin >> x1 >> c1 >> x2 >> c2 >> x3 >> c3;

		// red : true, blue : false
		x1 = (c1 == 'R' ? x1 : notX(x1));
		x2 = (c2 == 'R' ? x2 : notX(x2));
		x3 = (c3 == 'R' ? x3 : notX(x3));

		// ~x1 -> x2, ~x2 -> x1
		v[notX(x1)].push_back(x2);
		v[notX(x2)].push_back(x1);
		// ~x2 -> x3, ~x3 -> x2
		v[notX(x2)].push_back(x3);
		v[notX(x3)].push_back(x2);
		// ~x3 -> x1, ~x1 -> x3
		v[notX(x3)].push_back(x1);
		v[notX(x1)].push_back(x3);
	}
}

void dfs(int x) {
	low[x] = dfn[x] = ++node_num;
	s.push(x);

	for (int next : v[x]) {
		if (!dfn[next]) {
			dfs(next);
			low[x] = min(low[x], low[next]);
		}
		else if (!visited[next]) {
			low[x] = min(low[x], dfn[next]);
		}
	}

	if (low[x] == dfn[x]) {
		scc_Level++;
		while (1) {
			int p = s.top();
			s.pop();
			visited[p] = true;
			inDegree[p] = scc_Level;
			if (x == p) break;
		}
	}
}

void solve() {

	input();

	for (int i = 1; i <= 2 * N; i++) {
		if (!dfn[i]) dfs(i);
	}

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == inDegree[notX(i)]) {
			cout << -1;
			return;
		}
	}

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] < inDegree[notX(i)]) cout << "R";
		else cout << "B";
	}

}

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

	solve();

	return 0;
}