[C++] 백준 2207번: 가위바위보

문제 링크

2207번: 가위바위보

문제 요약

학생들은 원장 선생님이 가위바위보를 할때, 몇번째에 무엇을 낼지 2개의 선택을 할 수 있다. 이 두 선택 중 하나라도 맞으면 학생은 살아남게 된다. 원장 선생님이 주먹과 가위만 낸다고 할때, 모든 학생들이 살아남을 수 있는지 알아내야 한다.

접근 방법

학생들은 두 개의 선택 중에 하나만 맞히면 됩니다. 선생님은 가위와 바위만 내는데, 학생들의 두개의 선택을 $\vee$로 연결하고, 각 학생들의 선택을 $\wedge$로 연결하면 2-SAT 문제가 됩니다.

코드

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int MAX = 20001;
int n, m, visited[MAX], cnt = 0, scc_idx = 0, scc_num[MAX];
bool finished[MAX];
vector<int> adj[MAX];
stack<int> s;

int _not(int num) { return (num % 2 ? num - 1 : num + 1); }

int convert(int num) { return (num < 0 ? -(num + 1) * 2 : num * 2 - 1); }

int dfs(int next) {
	int res = visited[next] = ++cnt;
	s.push(next);

	for (auto& next : adj[next]) {
		if (!visited[next])
			res = min(res, dfs(next));
		else if (!finished[next])
			res = min(res, visited[next]);
	}

	if (res == visited[next]) {
		while (1) {
			int st = s.top();
			s.pop();
			finished[st] = true;
			scc_num[st] = scc_idx;
			if (st == next)
				break;
		}
		scc_idx++;
	}
	return res;
}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		x = convert(x), y = convert(y);
		adj[_not(x)].push_back(y);
		adj[_not(y)].push_back(x);
	}

	for (int i = 0; i < m * 2; i++)
		if (!visited[i])
			dfs(i);

	for (int i = 0; i < m; i++) {
		if (scc_num[i * 2] == scc_num[i * 2 + 1]) {
			cout << "OTL\n";
			return 0;
		}
	}

	cout << "^_^\n";
	return 0;
}