취미로 코딩하기

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

이번에 볼 문제는 백준 8310번 문제인 Riddle이다.
문제는 아래 링크를 확인하자.

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

각 i번째 town이 capital이면 true, 그렇지 않으면 false 값을 갖는 bool 변수 \(T_i\)를 생각해보자. 만약 문제의 조건들을 2-CNF로 표현이 가능하다면 문제를 2-SAT문제로 모델링해 해결할 수 있을 것이다. 아래는 문제의 조건들을 2-CNF로 표현하는 과정이다.

우선 "각 간선의 적어도 한쪽 끝은 capital이어야 한다" 조건은 두 town의 번호가 \(x\)와 \(y\)일 때 \((T_x \lor T_y)\)로 표현할 수 있다.

"각 country에는 capital이 정확히 하나씩 있어야한다"는 조건은 "각 country에는 capital이 최대 하나 존재한다" 및 "각 country에는 capital이 최소 하나 존재한다"는 두 조건으로 나누어 생각할 수 있다. 한편, 후자 조건 없이 전자 제약만을 걸어 답을 얻은 다음 capital이 정해지지 않은 국가의 경우 아무 도시나 capital로 지정한다면 후자 조건이 같이 있는 경우의 답을 얻을 수 있고 이는 어렵지 않으므로 후자 조건 없이 전자 조건만을 이용한 해를 찾는 것으로 문제를 해결할 수 있게 된다.

이제 "각 country에는 capital이 최대 하나 존재한다" 조건을 CNF로 표현해보자. 어떤 country에 속한 town이 \(T_{c_1}...T_{c_w}\)라 하자. naive하게 2-CNF로 이 조건을 표현하는 한 가지 방법은 모든 \(1 \leq i,j \leq w (i \neq j)\)에 대하여 \((T_{c_i} \lor T_{c_j})\) 들의 논리곱으로 나타내는 것이다. 그러니 이러한 모든 식을 이용하기에는 그래프의 크기가 매우 커지므로 다른 방법을 생각해야한다.

새로운 bool 변수 \(S_i\)를 정의해 그 값을 \(i\) 이하의 모든 \(T_{c_i}\) 들을 or한 값과 동치인 값으로 정의하자. 이 때 \(T_{c_i} \implies S_i \), \(S_i \implies S_{i+1}\) 및 \(S_i \implies ~T_{c_{i+1}} \)와 같은 논리관계를 부여하면 \(O(w)\)개의 노드 및 간선만을 추가해 위의 조건을 확인할 수 있게 된다. (자주 쓰이는 테크닉이므로 알아두자.)

위의 각 논리식들은 2-CNF로 나타낼 수 있으므로 2-SAT을 해결하는 선형 알고리즘을 이용해 이 문제를 해결할 수 있다. 시간복잡도는 \(O(N + M)\)이다.

그래프의 크기 및 입출력의 양이 많아 같은 알고리즘이더라도 속도가 느린 언어 또는 비효율적인 구현으로는 통과하기 어려운 듯하다. 이는 그래프를 모델링할 때 각 country에 capital이 최소 하나 존재 존재한다는 조건을 제외하고 별도의 처리로 조건을 만족시킨 이유이기도 하다. 혹시 그래도 시간 초과가 날 경우 불필요한 구현이 없는지 확인해 문제를 해결하자.

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

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

int N, M, K; const int gap = 2000000; // 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;
}

int nxtid;
vector<int> towns[1000001];

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

	cin >> N >> M >> K;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x + gap].emplace_back(y);
		G[y + gap].emplace_back(x);
	}

	nxtid = N;

	for (int k = 1; k <= K; k++) {
		int T; cin >> T;

		nxtid++;
		int old; cin >> old;
		G[old].emplace_back(nxtid);
		G[nxtid + gap].emplace_back(old + gap);

		towns[k].emplace_back(old);

		for (int t = 1; t < T; t++) {
			nxtid++;
			int x; cin >> x;
			G[x].emplace_back(nxtid);
			G[nxtid + gap].emplace_back(x + gap);
			G[nxtid - 1].emplace_back(nxtid);
			G[nxtid + gap].emplace_back(nxtid - 1 + gap);
			G[nxtid - 1].emplace_back(x + gap);
			G[x].emplace_back(nxtid - 1 + gap);
			
			towns[k].emplace_back(x);

			old = x;
		}
	}

	N = nxtid;

	if (TWOSAT()) {
		cout << "TAK\n";
		for (int k = 1; k <= K; k++) {
			bool has_capital = 0;
			for (auto t : towns[k]) {
				if (ans[t]) has_capital = 1, cout << t << ' ';
			}
			if (!has_capital) cout << towns[k].back() << ' ';
		}
	}
	else cout << "NIE";
}