백준 12893번 - 적의 적(C++)

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

12893번: 적의 적

 

문제를 처음 접했을 때 그래프 문제라는 것은 바로 파악할 수 있었다. 그러나 이 문제는 이분 그래프의 정석이라고 난이도 기여에서 말하던데 이분 그래프를 자세히 공부해본적이 없어서 조금 어려웠던 듯 하다. 우선 먼저 적대관계 그래프를 그려서 문제의 의미를 파악해보자. 

 

 

1 2

2 3

3 4

4 5

 

입력이 들어온다면 위와 같은 적대 그래프가 만들어질 것이다. 그리고 문제의 이론대로 우호 그래프를 완성해보면

 

 

다음과 같은 그래프가 완성된다. 그리고 여기서 같은 노드끼리지만 그래프가 두개로 확 나뉜것을 확인할 수 있다.

즉, 그래프의 파란색 간선과 빨간색 간선을 침범하는 입력이 들어오면 이론이 잘못된 것이다.

나는 여기서 적대그래프가 주어졌을 때 사이클이 존재하지 않으면 맞는 이론이라 생각했는데, 사이클의 존재 유무와 그래프의 겹치는지 안겹치는지는 중요치 않은 문제였다.

 

그래서 유니온 파인드를 통해 두개의 집합을 잘 나누고 관리하는 것이 문제의 핵심이다.

문제를 보며 알 수 있는 조건은

1. 한 번 우호거나 적대이면 절대 바뀌지 않는다.

2. 적의 적은 모두가 내 친구가 된다.

 

2번의 조건으로 입력들을 관리하고 1번 조건으로 정답을 결정한다.

 

글로 써보면

 

두 개의 적대관계 A, B 가 들어왔을 때,

A의 적대관계의 정점들은 모두 B의 우호관계로 편입하고

B의 적대관계의 정점들은 모두 A의 우호관계로 편입한다.

 

만약 적대관계가 없다면 상대방을 적대관계 정점으로 설정한다.

 

 

 

그런데 이런 의문이 들 수 있다. 

어라? 그렇다면 4의 입장에서 5는 적대관계인데 적대관계임을 명시해주지 않는다는 건가?

 

그렇다. 왜냐하면 만약 3 - 6 적대관계가 들어온다 해보자 

그렇다면 6번 정점은 3의 모든 적을 자기 우호관계로 편입시킨다. 그렇다면 3의 모든 적대관계인 2와 4를 모두 가지고 있어야할 것 같다. 하지만 우리는 유니온 파인드로 관리하고 있기 때문에 2번이나 4번만 가져와도 모든 우호관계를 가져오는 것이 된다.

 

그러므로 적대관계는 한개만 포함하고 있어도 괜찮다. 

 

이제 위의 글로 쓴 것을 슈도코드로 만들어보자

 

for(i = 0 ~ M){
	input a, b

	if (a와 b가 우호관계) -> 이론 불가능

	if (a와 적대관계인 정점이 존재함) b의 우호관계로 편입
	else (a가 적대관계인 정점이 없음) a의 적대관계로 b를 선언

	if (b와 적대관계인 정점이 존재함) a의 우호관계로 편입
	else (a가 적대관계인 정점이 없음) b의 적대관계로 a를 선언
}

 

우호관계 집합과 적대관계 집합을 위해 일반적인 유니온 파인드 par배열과 enermy배열을 선언하고 par에는 우호관계 표시를하고 enermy에는 각 정점의 적대관계를 표시하면 된다. 

 

#include <iostream>
#include <vector>
using namespace std; 
int par[2001];
int enermy[2001];

bool answer = true;
int N, M;
int Find(int a) {
	if (par[a] == a) return a;
	else return par[a] = Find(par[a]);
}
void Merge(int a, int b) {
	int par_a = Find(a);
	int par_b = Find(b);

	if (par_a < par_b) par[par_b] = par[par_a];
	else par[par_a] = par[par_b];
}

void init() {
	for (int i = 1; i <= N; i++) {
		enermy[i] = 0;
		par[i] = i;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N >> M;
	init();
	for (int i = 0; i < M; i++) {
		int s, e;

		cin >> s >> e;

		if (Find(s) == Find(e)) {
			answer = false;
			break;
		}

		if (enermy[s] == 0) {
			enermy[s] = e;
		}
		else {
			Merge(enermy[s], e);
		}

		if (enermy[e] == 0) {
			enermy[e] = s;
		}
		else {
			Merge(enermy[e], s);
		}
	}

	if (answer) cout << 1 << '\n';
	else cout << 0 << '\n';

	return 0;
}