[BOJ] 백준 17038. The Great Revegetation (Silver) (Gold II)

학교랭킹 랭작을 위해 풀은 문제인데, 꽤나 아이디어 면에서 얻어갈 게 많았다.

문제는 아래와 같다.

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

17038번: The Great Revegetation (Silver)

문제 요약 및 이해

S 1 2의 경우 1번 목초지와 2번 목초지는 같은 풀(?)을 심어야되고,

D 2 3의 경우 2번 목초지와 3번 목초지는 다른 풀(?)을 심어야 된다.

풀이라는 표현이 문제 번역과 맞는진 모르겠지만, 이하 풀이라고 쓰겠다.

따라서 경우의 수는 A A B로 심는 경우와 B B A로 심는 경우 두 가지로 나누어진다.

 

만약, S 1 2 / S 3 4/ D 2 5 / S 5 6의 경우라면 1 2 / 3 4 / 5 6끼리 같은 풀로 심되, 2와 5는 반드시 다른 풀로 심어야 한다.

따라서 경우의 수는 2*2=4가 답이다.

 

문제 해석은 어느정도 된 것 같으니,

아래에 해설을 작성하겠다.

---

의식의 흐름 및 해설

먼저, 알고리즘 분류는 대놓고 유니온파인드를 쓰라고 말하고 있는 문제이다.

따라서 유니온 파인드를 쓰면 되는데, D i j와 같이 D로 주어지는 경우 i에 심는 풀이 j에도 영향을 미친다.

이런 경우가 조금 골치아프다.

참고로 S i j와 같이 나올 경우는 단순히 merge만 해주면 된다.

 

따라서 D i j의 경우, i와 ~j를, 또는 j와 ~i를 merge해주자.

이쯤되면 2-sat가 생각날 것이다.

2-sat를 적용해주기 위해 1~N까지 뿐만 아니라 각각의 not형 (~형)을 위한 N+1~2N까지의 배열도 만들어주자.

 

그리고 정말 주의할 점.

1. 만약 i->~i일 경우, 모순이기 때문에 이때는 바로 0을 출력해주자.

2. (1번에서의 모순이 없음을 확인한 후에 진행해줘야 한다.) i -> ~j 와 j -> ~i를 같이 merge해주었기 때문에, 중복되는 경우를 없애주기 위해 i와 ~i를 하나의 parent로 만들어주자.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int MAX = 200011;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e6;
int N, M, p[MAX];
map<int, int> m;
int find(int a) {
	if (a == p[a])return a;
	return p[a] = find(p[a]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return false;
	if (a > b)swap(a, b);
	p[b] = a;
	return true;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	for (int i = 1; i <= N * 2; i++)p[i] = i;
	while (M--) {
		char ch;
		int n1, n2;
		cin >> ch >> n1 >> n2;
		if (ch == 'S') {
			merge(n1, n2);
			merge(n1 + N, n2 + N);
		}
		else {
			merge(n1, n2 + N);
			merge(n2, n1 + N);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (find(i) == find(i + N)) {
			cout << 0;
			return 0;
		}
	}
	for (int i = 1; i <= N; i++) {
		merge(i, i + N);
	}
	for (int i = 1; i <= N; i++) {
		m[find(i)]++;
	}
	cout << 1;
	for (int i = 0; i < m.size(); i++) {
		cout << 0;
	}
}

---

정말 오랜만에 2-sat를 복습한 듯한 느낌.

이참에 2-sat 문제도 나중에 함 풀어봐야겠다~