백준 12877번 문제 먹이 사슬 풀이

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

12877번: 먹이 사슬

설날 큰집을 가면서 노란책을 들고갔는데, 책을 보다가 나온 POJ문제 풀이를 보다가 혹시 백준에도 같은 문제가 있나 싶어서 확인해보니 있었다.

 

그래서 백준에 있는 김에 한번 풀어보았다.

 

POJ에서는 1182번 문제였는데, 직접 가보니까 중국어로 문제가 써있어서 해석은 안된다 싶었는데, Sample Input 까지도 일치하더라. 대신 크롬에 내장된 구글 번역기를 사용하니 그런대로 해석은 되는 듯 하다.

 

 

 

문제 분석

일단 나는 책을 보면서 문제를 봤기 때문에, 풀이를 거의 바로 보아서 힌트 없이 스스로 생각해볼 만한 시간이 조금 부족하긴 했다.

 

대충 보면 명제와 관련된 문제이고, 논리와도 관련이 있다. 여태까지의 정보를 조합해서 모순이 되는 논리를 찾아야 한다.

 

내가 풀고나서 찍은 스샷이니, 내가 풀 당시에는 15명밖에 안푼 문제이기도 하다.

 

일단 풀이부분은 스포일러 방지로 접은글로 표현하겠다.

 

풀이

논리식을 만들어서, 같이 성립될 수 있는 논리들을 묶는 방식으로 풀이를 진행한다. Union-Find라고 불리는 Disjoint set 자료구조를 이용해서 묶으면 된다.

 

동물의 번호를 0 ~ N-1까지 매긴다고 하면, 3N개의 논리를 만든다.

각각 i번 동물이 A 종류이다 / B종류이다 / C종류이다. 라는 논리들이다.

 

만약 N = 3이라고 한다면

0번 - 0번 동물이 A종류이다.

1번 - 1번 동물이 A종류이다.

2번 - 2번 동물이 A종류이다.

 

3번 - 3번 동물이 B종류이다.

4번 - 4번 동물이 B종류이다.

5번 - 5번 동물이 B종류이다.

 

6번 - 6번 동물이 C종류이다.

7번 - 7번 동물이 C종류이다.

8번 - 8번 동물이 C종류이다.

 

요런식으로 구분이 되게 된다.

그러면 주어진 정보에 따라서 적절한 정보들을 Union 연산을 하는데, 만약 모순되는 내용이 같은 집합에 들어가게 된다면 무시하고 답 수를 1만큼 늘려야 한다.

 

x번 동물과 y번 동물이 같은 종류이다 라는 명제가 들어왔을때, 이미 두 동물이 다른 종류이다 라는 명제가 동시에 성립한다면(같은 집합 안에 있다면) 이번 명제는 모순이 되는 것이다.

다른 동물일 수 있는 경우의 수는 전체 경우의 수 3x3 = 9가지 중 6가지가 해당되게 된다.

 

x번 동물이 y동물을 잡아먹는다고 하면, 마찬가지로 6가지 모순인 경우의 명제가 이미 같이 성립하고 있다면 이번 명제가 모순이 되게 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define MAXN 50020

// disjoint set (DSU)
int parent[MAXN * 3];
int depth[MAXN * 3];

int root(int a) {
	int p = a;
	while (p != parent[p])
		p = parent[p];
	parent[a] = p;
	return p;
}
bool same(int a, int b) {
	return root(a) == root(b);
}
void unite(int a, int b) {
	a = root(a);
	b = root(b);
	if (a == b) return;
	if (depth[a] < depth[b]) {
		parent[a] = b;
	}
	else {
		parent[b] = a;
		if (depth[a] == depth[b])
			depth[b]++;
	}
}
int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	//init
	for (int i = 0; i <= N * 3 + 10; i++) {
		parent[i] = i;
		depth[i] = 0;
	}
	// i => i는 A이다.
	// i + N => i는 B이다.
	// i + N*2 => i는 C이다.
	int ans = 0;
	while (K--) {
		int t, a, b;
		scanf("%d%d%d", &t, &a, &b);
		a--;
		b--;
		if (a < 0 || b < 0 || a >= N || b >= N) {
			ans++;
			continue;
		}
		if (t == 1) {
			//a랑 b랑 같은 종류이다.
			if (same(a, b + N) || same(b, a+N) || same(a+N, b+N+N) || same(b+N, a+N+N) ||
				same(a, b + N + N) || same(b, a + N + N)) {
				ans++;
			}
			else {
				unite(a, b);
				unite(a + N, b + N);
				unite(a + N + N, b + N + N);
			}
		}
		else {
			//a는 b를 잡아먹는다.
			if (same(a, b) || same(a + N, b + N) || same(a + N + N, b + N + N) ||
				same(a, b + N + N) || same(a + N, b) || same(a + N + N, b + N)) {
				ans++;
			}
			else {
				unite(a, b + N);
				unite(a + N, b + N + N);
				unite(a + N + N, b);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

노란책의 솔루션 코드를 보면, 조건을 6개를 다 명시하지 않아도 정답이 된다고 하는데 왜 그런지는 아직 이해가 안된다;;

if (t == 1) {
	//a랑 b랑 같은 종류이다.
	//if (same(a, b + N) || same(b, a + N) || same(a + N, b + N + N) || same(b + N, a + N + N) ||	same(a, b + N + N) || same(b, a + N + N)) {
	if (same(a, b+N) || same(a, b+N+N)) {
		//다른걸로 분류하면 모순
		ans++;
	}
	else {
		unite(a, b);
		unite(a + N, b + N);
		unite(a + N + N, b + N + N);
	}
}
else {
	//a는 b를 잡아먹는다.
	//if (same(a, b) || same(a + N, b + N) || same(a + N + N, b + N + N) || same(a, b + N + N) || same(a + N, b) || same(a + N + N, b + N)) {
	if (same(a,b) || same(a, b+N+N)) {
		ans++;
	}
	else {
		unite(a, b + N);
		unite(a + N, b + N + N);
		unite(a + N + N, b);
	}
}

이 코드로도 정답이 되는데 왜 그런지는 아직 이해가 안간다. 천천히 이해해봐야할듯 하다.