[백준 3648] 아이돌

문제 링크 => 3648번: 아이돌 (acmicpc.net)

3648번: 아이돌

 

2-SAT 문제이다.

 

각 심사위원은 자신이 행사한 두 표 중 적어도 하나는 결과에 영향을 미쳐야 한다고 생각을 한다.

두 표 모두와 반대되는 결과가 나오면, 심사위원은 투표 결과에 대해서 의심을 하게 된다.

 

즉, 두 표 모두와 반대되는 결과가 나오면 투표 결과에 대해서 의심을 하게 되는데 이를 방지해야 한다.

예를 들어서 심사위원 X 가 1번째 참가자(A) 에게 찬성, 2번째 참가자(B) 에게 반대를 던졌다고 하자.

그렇다면 f(A, B) = A ∨ B' 을 만족해야 한다.

 

 f(A, B) = A ∨ B' 에 대해서

(1) A = 찬성, B = 반대   =>   f(A, B) = 의심 x

(2) A = 찬성, B = 찬성   =>   f(A, B) = 의심 x

(3) A = 반대, B = 반대   =>   f(A, B) = 의심 x

(4) A = 반대, B = 찬성   =>   f(A, B) = 의심 o  (두 표 모두와 반대되는 결과!)

 

상근이는 심판들이 자신의 프로그래밍 능력에 큰 관심을 보이지 않을 것 같아 걱정하고 있다.

따라서, 상근이는 해킹을 이용해서 다음 라운드에 진출하려고 한다. 

 ...

참가자의 번호는 1번부터 n번이다. 상근이는 1번 참가자이다. 

 

그리고 상근이가 1번 참가자로 참가하여 다음 라운드에 진출하는 것까지 고려해야 한다.

즉, 코사라주 알고리즘을 이용하여 문제를 접근한다고 할 때 SCC를 만드는 과정에서

inDegree[1] < inDegree[not(1)] 를 만족하게 될 경우 상근이는 탈락하게 된다.

 

따라서 이 문제를 해결하기 위해서

(1) SCC 내에서 x, not(x) 가 묶여있는지 확인한다.      

       x ~> x', x' ~> x 일 경우 2-sat formula를 만족시키지 못하므로 "no" 를 출력한다.

(2) inDegree[1] > inDegree[not(1)] 를 만족해야 한다.

     만족하지 못할 경우 상근이는 자동으로 탈락하게 되므로 두 표 모두와 반대되는 결과를 만족함에도

     불구하고 "no" 를 출력한다.

 

(1) 에서 x, not(x)가 묶여있지 않고 (2) 를 만족하게 될 경우 이 경우는 "yes" 이다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<int> go[2001], back[2001];
vector<vector<int>> SCC;
stack<int> S;
int n, m;
int inDegree[2001];
bool visited[2001];

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

void dfs1(int x) 
{
	if (visited[x])
		return;
	visited[x] = true;
	for (int next : go[x]) {
		dfs1(next);
	}
	S.push(x);
}

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

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

void all_initialize()
{
	int i;

	initialize();
	for (i = 1; i <= 2 * n; i++) {
		go[i].clear();
		back[i].clear();
		inDegree[i] = 0;
	}
	SCC.clear();
}

const char* solution()
{
	int i;

	for (i = 1; i <= 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);
		}
	}

	initialize();

	for (vector<int> v : SCC) {
		for (int x : v) {
			visited[x] = true;
		}
		for (int x : v) {
			if (visited[x] && visited[notX(x)])
				return "no";
		}
		for (int x : v)
			visited[x] = false;
	}

	if (inDegree[1] < inDegree[notX(1)])
		return "no";

	return "yes";
}

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

	int x, y, i;
	while (scanf("%d", &n) != EOF) {
		scanf("%d", &m);
		all_initialize();
		for (i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			x = (x < 0 ? n - x : x);
			y = (y < 0 ? n - y : y);

			// ~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));
		}
		printf("%s\n", solution());
	}

	return 0;
}