취미로 코딩하기

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

이번에 볼 문제는 백준 27503번 문제인 요가 수업이다.
문제는 아래 링크를 확인하자.

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

주어진 조건으로부터, 꼭 지켜져야 하는 규칙들은 다음과 같이 요약할 수 있다:

(1) \(M\)개의 동작 중, 대응되는 대체 동작이 있는 동작은 원래 동작과 대체 동작 중 적어도 하나의 동작을 해야 한다.

(2) \(M\)개의 동작 중, 대응되는 대체 동작이 없는 동작은 무조건 해야 한다.

(3) \(K\)가지 쌍에 해당하는 동작들은 두 동작 중 적어도 하나의 동작을 하지 않아야 한다.

위와 같은 위의 내용을 CNF로 치환하면 이 문제는 2-SAT문제로 변환된다. 따라서 주어진 문제를 implication graph로 변환 후 SCC를 구해 모순이 발생하는지 확인하는 것으로 문제를 선형시간에 해결할 수 있다.

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

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

int N, M, C, K;
bool chk[500001];
vector<int> G[1000001];
int dfidx, dfi[1000001];
int scidx, sci[1000001];
vector<int> stk;

int dfs(int cur) {
	stk.emplace_back(cur);
	int ret = dfi[cur] = ++dfidx;
	for (auto &nxt : G[cur]) {
		if (sci[nxt]) continue;
		if (dfi[nxt]) ret = min(ret, dfi[nxt]);
		else ret = min(ret, dfs(nxt));
	}
	if (ret == dfi[cur]) {
		scidx++;
		while (stk.back() != cur) {
			sci[stk.back()] = scidx;
			stk.pop_back();
		}
		sci[stk.back()] = scidx;
		stk.pop_back();
	}
	return ret;
}

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

	cin >> N >> M >> C >> K;
	while (M--) {
		int x; cin >> x;
		chk[x] = 1;
	}
	while (C--) {
		int x, y; cin >> x >> y;
		G[x + 500000].emplace_back(y);
		G[y + 500000].emplace_back(x);
		chk[x] = chk[y] = 0;
	}
	while (K--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y + 500000);
		G[y].emplace_back(x + 500000);
	}
	for (int i = 1; i <= N; i++) {
		if (chk[i]) G[i + 500000].emplace_back(i);
	}

	for (int i = 1; i <= N; i++) {
		if (!sci[i]) dfs(i);
		if (!sci[i + 500000]) dfs(i + 500000);
	}
	for (int i = 1; i <= N; i++) {
		if (sci[i] == sci[i + 500000]) {
			cout << "NO";
			return 0;
		}
	}

	cout << "YES";
}