백준 11280 2-SAT - 3 (c++) : 피너클

11280번: 2-SAT - 3

https://www.acmicpc.net/problem/11280

 

SCC를 이용해서 풀었다.

 

(P ∧ ¬Q) ¬P ∨ Q

 

(A ∧ B) 이거는 A and B 이거다.

(A ∨ B) 이거는 A or B 이거다.

문제는 (A ∨ B) ∧ (A ∨ B) ∧ (A ∨ B) ∧ (A ∨ B) 이런 식으로 나온다.

즉 (A ∨ B) 이게 무조건 True 여야한다.

 

이제 (A ∨ B) 이걸 (¬A → B) ∧ (¬B → A) 이렇게 바꿔야 한다.

그러기 위해서는 먼저 A → B 이게 뭔지를 알아야 한다.

 

A → B 이건 조건문이다. "A 이면 B이다" 이런식으로 가는 것이다.

A가 "비가 온다" B가 "우산을 쓴다" 이렇게 가고

A가 True고 B가 True면

"비가온다" 그러니 "우산을 쓴다" 이렇게 되는것이다.

 

만약 A가 True고 B가 False면 

"비가 온다" 그런데 "우산은 안쓴다" 이건 딱봐도 뭔가 이상하다.

 

True -> True = True이고 

True -> Fasle는 False이다.

 

근데 만약 A가 False면 어떨까

A가 False면 무조건 True다.

False -> True = True

False -> False = True

왜 무조건 True일까? 이건 그냥 약속이다.

A가 False면 무조건 True로 하기로 약속한거다. 누가 약속했는지는 모른다.

이제 A -> B에서 -> 가 뭘 하는 놈인지 알았다.

 

(¬A → B)여기에서 ¬ 이건 그냥 ! 이거다.

!True = False 이렇게 되는것처럼 ¬True = False이렇게 되는거다. 반전 시키는거다.

 

우리의 목표 (A ∨ B) 이걸 (¬A → B) ∧ (¬B → A) 이렇게 바꾸는거, 이제 거의 다 왔다.

A -> B를 말로하면 "A가 참이면 B도 참이어야한다."

이걸 반대로 말하면

"A가 참인데 B가 거짓이면 거짓이 된다" 이렇게 된다.

이건

"A가 참인데 B가 거짓인 상황은 전체 명제가 거짓이 된다."

이렇게 변하고 이걸 논리식으로 표현하면

¬ (A ∧ ¬ B) 이렇게 된다.

A가 참이고 B가 거짓이라 가정하자 B앞에 ¬이게 있으니 ¬B는 참이되고

참 and 참 -> 참이 된다. 근데 맨 앞에 ¬이게 있으니 ¬참 -> 거짓 이 되어버린다.

나머지도 전부 해보면 ¬ (A ∧ ¬ B) 이것이 A -> B 이것과 정확히 같다는걸 알수있다.

 

이제 ¬ (A ∧ ¬ B)이걸 드모르간 법칙을 이용해 ¬A ∨ B 이렇게 바꿔준다.

드모르간 법칙은 미안하지만 다른곳에서 봐줘라

 

우리의 목표 (A ∨ B) 이걸 (¬A → B) ∧ (¬B → A) 이렇게 바꾸는거, 진짜 거의 다 왔다.

우리느 A->B가 ¬A ∨ B 이거인걸 알고잇다.

그럼 (¬A → B) 이거는 ( A ∨ B) 이게 된다. A에 ¬이게 붙었으니 말이다.

(¬B → A)는 ( B ∨ A) 이게 된다.

 (¬A → B) ∧ (¬B → A) 이거는 ( A ∨ B)  ∧ ( B ∨ A) 이거랑 같다.

 

( A ∨ B)  ∧ ( B ∨ A)이거에서 ( A ∨ B) 랑 ( B ∨ A)는 그냥 같다 순서만 다른거다.

그러니 뒤에 있는 (B ∨ A) 이걸 없애면

( A ∨ B) 이것만 남는다.

 

이제 이걸 거꾸로 가면 된다.

(A ∨ B) 이거는 ( A ∨ B)  ∧ ( B ∨ A) 이거고 

( A ∨ B)  ∧ ( B ∨ A) 이거는  (¬A → B) ∧ (¬B → A) 이거다.

 

사전 준비는 끝났다. 우리는 → 이거를 그래프를 통해서 표현할 것이다.

근데 그래프를 통해서 뭘 어떻게 표현할까

 

백준에 있는 예제로 그래프를 그려보자

 

 

1 2
1 1
-1 -1

두번째 예제이다.

graph[notValue(1)].push_back(1) 이걸 하면

graph[10001].push_back(1) 이렇게 들어가게된다.

-1들은 valueToIndex에서 10001로 변환된다.

graph[notValue(10001)].push_back(10001) 이걸하면

graph[1].push_back(10001) 이렇게 들어간다.

 

이런 그래프가 완성된다. 

이 그래프가 의미하는건 (1 -> -1)과 (-1 -> 1) 이것이다.

1이 True면 -1은 1의 반대이니 False여야하고 1이 False면 -1은 True여야한다.

 

(True -> False)는 False이다. 결국 위의 그래프는 무조건 False를 반환할수밖에없다.

우리가 SCC를 하는 이유가 여기에 있다.

한 그룹내에 i와 i의 역수가 함께 있으면 그 그룹에는 모순이 발생한다.

그래서 우리가 SCC를 통해 그룹을 만들어 확인하는 것이다.

 

int n, m;
int dfsn[20001];
bool finished[20001];
int sn[20001];
vector<int> graph[20001];
vector<vector<int>> SCC;
vector<int> stack;
int cnt, SN;

사용할 변수들이다. 거의다 SCC에 사용한다.

 

int notValue(int num) {
	if (num > 10000) return num - 10000;
	else return num + 10000;
}

int valueToIndex(int num) {
	if (num < 0) return -num + 10000;
	else return num;
}

이것도 설명해야한다.

실제로 입력이 들어오는건 -10000 ~ 10000사이의 숫자들이다.

-1과 1은 서로 ¬ 관계이다. ¬1 = -1 이다.

이걸 어떻게 배열 안에 집어넣느냐, 그걸 하기 위한 함수가 위의 함수다.

valueToIndex() 안에 1을 넣으면 1을 반환한다.

valueToIndex() 안에 -1을 넣으면 10001을 반환한다.

이렇게 해서 우린 배열 안에 값을 넣을 수가 있다.

 

문제는 우리는 각 숫자에 ¬이걸 해야한다. 각 숫자를 반전해야한다.

반전하는 함수가 notValue함수이다.

notValue()안에 1을 넣으면 10001을 반환한다.

notValue()안에 10001을 넣으면 1을 반환하다.

정확히 1과 -1의 ¬를 반환하는 것이다.

 

이렇게 생각하면 된다.

-1 -> 10000 + 1

-2 -> 10000 + 2

-3 -> 10000 + 3

이렇게 바꾸는거다.

1은 1이고 -1은 10000 + 1이고

10001에 10000을 빼면 1이고

1에 10000을 더하면 10001이고

int dfs(int now) {
	dfsn[now] = ++cnt;
	stack.push_back(now);

	int parent = dfsn[now];
	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];
		if (dfsn[next] == 0) parent = min(parent, dfs(next));
		else if (!finished[next]) parent = min(parent, dfsn[next]);
	}

	if (parent == dfsn[now]) {
		vector<int> scc;
		while (!stack.empty()) {
			int t = stack.back();
			stack.pop_back();
			scc.push_back(t);
			finished[t] = true;
			sn[t] = SN;
			if (t == now) break;
		}
		SCC.push_back(scc);
		SN++;
	}
	return parent;
}

이건 SCC함수인데 자세한 설명은 생략한다.

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	SN = 0;
	cnt = 1;

SCC에 사용하는 변수들 세팅하고

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x1, x2;
		cin >> x1 >> x2;
		x1 = valueToIndex(x1);
		x2 = valueToIndex(x2);
		graph[notValue(x1)].push_back(x2);
		graph[notValue(x2)].push_back(x1);
	}

변수들 입력받고 함수들을 이용해서 변환해준다.

graph[A].push_back(B)를 하면 A->B를 의미한다.

	for (int i = 1; i <= 20000; i++) dfsn[i] = 0;
	for (int i = 1; i <= 20000; i++) if (dfsn[i] == 0) dfs(i);

그 다음에는 SCC구한다음에

	for (int i = 1; i <= 20000; i++) {
		if (sn[i] == sn[notValue(i)]) {
			cout << 0 << '\n';
			return 0;
		}
	}
	cout << 1 << '\n';
	return 0;
}

i랑 notValue(i)랑 같은 SCC안에 들어있으면 0을 출력하고 아니면 1을 출력한다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
int dfsn[20001];
bool finished[20001];
int sn[20001];
vector<int> graph[20001];
vector<vector<int>> SCC;
vector<int> stack;
int cnt, SN;

int notValue(int num) {
	if (num > 10000) return num - 10000;
	else return num + 10000;
}

int valueToIndex(int num) {
	if (num < 0) return -num + 10000;
	else return num;
}

int dfs(int now) {
	dfsn[now] = ++cnt;
	stack.push_back(now);

	int parent = dfsn[now];
	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];
		if (dfsn[next] == 0) parent = min(parent, dfs(next));
		else if (!finished[next]) parent = min(parent, dfsn[next]);
	}

	if (parent == dfsn[now]) {
		vector<int> scc;
		while (!stack.empty()) {
			int t = stack.back();
			stack.pop_back();
			scc.push_back(t);
			finished[t] = true;
			sn[t] = SN;
			if (t == now) break;
		}
		SCC.push_back(scc);
		SN++;
	}
	return parent;
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	SN = 0;
	cnt = 1;

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x1, x2;
		cin >> x1 >> x2;
		x1 = valueToIndex(x1);
		x2 = valueToIndex(x2);
		graph[notValue(x1)].push_back(x2);
		graph[notValue(x2)].push_back(x1);
	}
	for (int i = 1; i <= 20000; i++) dfsn[i] = 0;
	for (int i = 1; i <= 20000; i++) if (dfsn[i] == 0) dfs(i);

	for (int i = 1; i <= 20000; i++) {
		if (sn[i] == sn[notValue(i)]) {
			cout << 0 << '\n';
			return 0;
		}
	}
	cout << 1 << '\n';
	return 0;
}

전체코드다.