boj, 백준) 13344. Chess Tournament (C/C++)

1. 문제 링크

www.acmicpc.net/problem/13344

13344번: Chess Tournament

 

2. 문제 개요

체스 대회에서 출전자들이 심판을 본다. 그런데 이게 출전자들이 심판을 보다 보니 진짜인지 가짜인지 알 방법이 없다.

각자 체스 능력이 > or =로 주어지고 각 스탯이 높은 사람은 스탯이 낮은 사람과 경기를 할 경우 무조건 이기게 된다.

각 스탯이 주어질 때, 결과가 일관적인지, 일관적이지 않은지 구분하는 프로그램을 작성하시오.

 

3. 문제 힌트

기술(skills)의 우월이 정해지는 경우는 간선으로 나타내어 연결하자.

능력이 같다고 주어지는 경우는 disjoint set(서로소 집합, 분리집합)을 사용하여 완전 같은 사람으로 생각해보자

 

주어지는 맵은 위상 정렬로 검증해보자. 정렬이 되지 않으면 어딘가 cycle이 있다거나 거짓이 있다는 것.

 

 

4. 문제 풀이

서로소 집합을 사용해서 만약, 1 = 2가 주어졌다 하고 2 > 3이 주어지는 경우, 2의 부모를 1로 하여 마치 1 > 3 인 것처럼 연결해주면 된다.

 

1이 2를 이기고, 2가 3을 이기고, 3이 1을 이기는 것과 같은 예는 나올 수가 없다. 일반적인 경기라면 충분히 나올 수 있는데, 기술(skill) or 스탯이라고 해야 할까, 능력이 높으면 무조건 이기기 때문이다.

그래서  = 가 나오면 그냥 아예 똑같은 노드라고 생각해주자.

 

반례

처음에 이런 예를 고려 안 해서 틀렸다.

완전 똑같은 노드라고 처리하지 않고 그냥 느슨하게만 같은 노드다 라고 처리해줬기 때문에,

검증 단계에 위상 정렬로 문제를 발견할 수 없었다. 

 

개선

위처럼, 1, 3이 각각 노드의 대표라고 했을 때, 대표가 아닌 노드(2, 4)가 갖고 있는 간선을 모두 대표(1, 3)에게 옮겨 주어야 한다. 그러면 cycle이 발생되는 것을 알 수 있고 위상정렬로 문제를 발견할 수 있다.

 

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

struct DISJOINTSET {

	DISJOINTSET() {}
	DISJOINTSET(int size) {
		parent.resize(size);
		for (int i = 0; i < size; ++i)
			parent[i] = i;
	}

	int find(int node){
		if (node == parent[node])
			return node;

		return parent[node] = find(parent[node]);
	}

	void union_set(int src, int dst){

		src = find(src);
		dst = find(dst);

		parent[dst] = src;
		return;
	}

	vector<int> parent;
};

int n, m, chk, rootnum;
vector<vector<int>> adj;
vector<int> indegree;
vector<pair<int,int>> edge;
queue<int> q;
bool consistent = true;

int main()
{
	scanf("%d %d", &n, &m);
	adj.resize(n);
	indegree.resize(n);
	DISJOINTSET disjoint(n);

	for (int i = 0; i < m; ++i) {
		int to, from;
		char ret;
		scanf("%d %c %d", &to, &ret, &from);

		if (ret == '>') {
			edge.push_back({ to,from });
		}
		else{
			disjoint.union_set(to, from);
		}
	}
	
	for (int i = 0; i < edge.size(); ++i) {
		int p_from, p_to;
		p_from = disjoint.find(edge[i].second);
		p_to = disjoint.find(edge[i].first);
		adj[p_from].push_back(p_to);
		++indegree[p_to];
	}
	

	for (int cur = 0; cur < n; ++cur) {
		if (cur == disjoint.parent[cur]){
			rootnum++;
			if (indegree[cur] == 0)
				q.push(cur);
		}
	}

	while (!q.empty()) {
		int cur = q.front(); q.pop();
		++chk;

		for (int next : adj[cur]) {
			if (disjoint.find(cur) == disjoint.find(next))
				consistent = false;

			--indegree[next];
			if (indegree[next] == 0)
				q.push(next);
		}
	}
	
	
	if (chk == rootnum && consistent == true)
		printf("consistent");
	else
		printf("inconsistent");

	

	return 0;
}

 

6. 결과