boj, 백준) 2-SAT - 1

1. 문제 링크

www.acmicpc.net/problem/11277

11277번: 2-SAT - 1

2. 문제 개요

2-SAT를  풀어보자.

SAT에 대한 설명은 본문에 잘 나와있다.

 

3. 문제 힌트

N은 최대 20,

M은 최대 100,

전수조사로 충분히 풀 수 있는 크기이다.

 

시간 복잡도는 모든 경우의 수 (2^20)에 대해 M개의 식을 검증하면 된다.

O(2^(N)*M)인데 간당간당..

 

4. 문제 풀이

dfs방식으로 모든 순열을 만들어내자.

그 후, 모든 상태(True/False)가 결정되면 검증을 진행하자.

 

홈페이지에 백트래킹도 사용할 수 있다고 나오던데.. 적용하려면 조금 더 복잡해질 것 같아서 하지 않았다.

 

5. 코드

#include <cstdio>
#include <vector>
using namespace std;

int n, m, ans;
vector<pair<int, int>> v;
vector<bool> state;

void dfs(int depth) {

	if (depth == n + 1) {

		bool chk = true;
		for (int i = 1; i < v.size(); ++i)
		{
			bool l, r;
			if (v[i].first < 0)
			{
				l = !state[-v[i].first];
			}
			else
			{
				l = state[v[i].first];
			}

			if (v[i].second < 0) {

				r = !state[-v[i].second];
			}
			else
			{
				r = state[v[i].second];
			}

			if (l == false && r == false)
				chk = false;


		}
		if (chk) 
			ans = 1;
		

		return;
	}

	for (int i = 0; i < 2; ++i) {
		if (i == 0) {
			state[depth] = true;
		}
		else {
			state[depth] = false;
		}
		dfs(depth + 1);
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	v.resize(m + 1);
	state.resize(n + 1, true);

	for (int i = 1; i <= m; ++i)
		scanf("%d %d", &v[i].first, &v[i].second);

	dfs(1);

	printf("%d", ans);

	return 0;
}

 

6. 결과