취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16915번 문제인 호텔 관리이다.
문제는 아래 링크를 확인하자.

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

어떤 열린 방에 스위치 s1, s2가 연결되어있다고 하자. 이 때, 이 방을 열린 상태로 유지하기 위해서는 두 스위치 s1과 s2는 동시에 켜져있거나 동시에 꺼져있어야 한다. 즉 s1이 켜져있다면 s2 또한 켜져있어야 하고, s2가 켜져있다면 s1 또한 켜져있어야 하며, s1이 꺼져있다면 s2 또한 꺼져있어야 하고, s2가 꺼져있다면 s1 또한 꺼져있어야 한다.

비슷하게, 어떤 닫힌 방에 스위치 s1, s2가 연결되어있다고 하자. 이 때, 이 방을 열린 상태로 만들기 위해서는 두 스위치 s1과 s2 둘 중 하나는 켜져있어야 하고 하나는 꺼져있어야 한다. 즉 s1이 켜져있다면 s2는 꺼져있어야 하고, s2가 켜져있다면 s1은 꺼져있어야 하고, s1이 꺼져있다면 s2는 켜져있어야 하고, s2가 꺼져있다면 s1은 켜져있어야 한다.

위의 조건들을 CNF(논리곱 표준형)들로 생각하면 문제의 상황을 2-SAT 문제로 모델링할 수 있다. 해당 2-SAT 문제의 해가 존재하는지를 판단해 문제를 해결하자.

아래는 제출한 소스코드이다.

#define NODE 200001
#include <iostream>
#include <vector>
#include <string>
#include <utility>
using namespace std;

int N, M; const int gap = 100000; // 2-SAT 정점개수(TF분할 말고), T와F노드 사이 값의 차이
vector<int> G[NODE];
int dfi[NODE]; int dfidx = 1;
int sci[NODE]; int scidx = 1;
vector<int> stk;
int twosatdfs(int current) {
	stk.emplace_back(current);
	int ret = dfi[current] = dfidx++;
	for (auto node : G[current]) {
		if (sci[node]) continue;
		if (dfi[node]) ret = min(ret, dfi[node]);
		else ret = min(ret, twosatdfs(node));
	}

	if (ret == dfi[current]) {
		while (stk.back() != current) {
			sci[stk.back()] = scidx;
			stk.pop_back();
		}
		sci[stk.back()] = scidx++;
		stk.pop_back();
	}

	return ret;
}

bool ans[NODE];
bool TWOSAT() {
	for (int i = 1; i <= N; i++) {
		if (sci[i]) continue;
		twosatdfs(i);
	}
	for (int i = 1 + gap; i <= N + gap; i++) {
		if (sci[i]) continue;
		twosatdfs(i);
	}

	for (int i = 1; i <= N; i++) {
		if (sci[i] < sci[i + gap]) ans[i] = 1;
		else if (sci[i] > sci[i + gap]) ans[i] = 0;
		else return 0;
	}
	return 1;
}

bool is_open[100001];
vector<int> switches[100001];

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

	cin >> M >> N;

	for (int i = 1; i <= M; i++) cin >> is_open[i];
	for (int i = 1; i <= N; i++) {
		int K; cin >> K;
		while (K--) {
			int x; cin >> x;
			switches[x].emplace_back(i);
		}
	}

	for (int i = 1; i <= M; i++) {
		int x = switches[i][0], y = switches[i][1];
		if (is_open[i]) {
			G[x].emplace_back(y);
			G[y].emplace_back(x);
			G[x + gap].emplace_back(y + gap);
			G[y + gap].emplace_back(x + gap);
		}
		else {
			G[x].emplace_back(y + gap);
			G[y].emplace_back(x + gap);
			G[x + gap].emplace_back(y);
			G[y + gap].emplace_back(x);
		}
	}

	cout << TWOSAT();
}