[백준 2207] 가위바위보

문제 링크 => 2207번: 가위바위보 (acmicpc.net)

2207번: 가위바위보

---

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

 

이 문제의 핵심은 학생들은 가위, 바위만 낼 수 있고 학생이 i 번째와 j 번째에 가위, 바위 둘중에 하나를 랜덤으로 선택할 때 둘중 하나는 무조건 맞아야 한다.

 

이때, i 번째에 예상하는 것을 xi, j 번째에 예상하는 것을 xj 라고 할 때, (xi v xj) 가 True 이기 위해서 ~xi -> xj 또는 ~xj -> xi 가 True 임을 만족하면 된다. 

 

즉, (xi1 v xj1) ^ (xi2 v xj2) ^ ... ^ (xin v xjn) => (~xi1 -> xj1) ^ (~xi2 -> xj2) ^ ... ^ (~xin -> xjn) 임을 만족하도록 하면 된다.

 

그리고 가위와 바위에 대한 처리는 가위를 true, 바위를 false 로 처리하면 된다.

 

즉, 원장선생님이 5번 혼자서 가위바위보를 했다고 가정할 때 3번째에 가위 5번째에 바위라고 한다면 3번째 가위를 3, 5번째 바위를 ~5 = 5+5 = 10 으로 표현하고 이를 연결하면 (x3 v x10) => (~x3 -> x10) => (x8 => x10) 이다.

 

풀이 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>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M;
vector<int> go[20001], back[20001];
int inDegree[20001];
bool visited[20001];
stack<int> s;
vector<vector<int>> SCC;

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

void dfs1(int x) {
	if (visited[x]) return;
	visited[x] = true;
	for (int i = 0; i < go[x].size(); i++) {
		int next = go[x][i];
		dfs1(next);
	}
	s.push(x);
}

void dfs2(int x, vector<int>& v) {
	if (visited[x]) return;
	visited[x] = true;
	for (int i = 0; i < back[x].size(); i++) {
		int next = back[x][i];
		dfs2(next, v);
	}
	v.push_back(x);
	inDegree[x] = SCC.size();
}

void initialize() {
	for (int i = 1; i <= M; i++) {
		visited[i] = visited[i + M] = false;
	}
}

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

	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		if (x < 0) x = abs(x) + M;
		if (y < 0) y = abs(y) + M;

		// ~x -> y
		go[notX(x)].push_back(y);
		back[y].push_back(notX(x));

		// ~y -> x
		go[notX(y)].push_back(x);
		back[x].push_back(notX(y));
	}

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

	initialize();

	while (!s.empty()) {
		int x = s.top();
		s.pop();
		if (!visited[x]) {
			vector<int> v;
			dfs2(x, v);
			SCC.push_back(v);
		}
	}

	for (int i = 1; i <= M; i++) {
		if (inDegree[i] == inDegree[notX(i)]) {
			cout << "OTL";
			return;
		}
	}

	cout << "^_^";
}

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

	solve();

	return 0;
}