백준 13344번 Chess Tournament

문제

Your friend is an organizer of the International Chess Playing Championship. He is worried that some of the contestants may be cheating, and he has asked you to help out. The chess players are allowed to report matches to the jury themselves, and this is not checked with the reported opponent. So, it is possible for competitors to make up matches and falsely report themselves as the winners.

Since chess is a game of skill, and not of chance, a player will always beat their opponent if their skill level is higher. A game will result in a draw if and only if the two players’ skills are exactly equal.

However, the skill level of the players is not known. He has therefore asked you to write a program that, given a list of reported matches, determines whether this list is consistent or not. The list is inconsistent if we can determine that at least reported match is falsely reported, otherwise it is consistent.

문제풀이

사용한 알고리즘 : 위상정렬

(0) 생각

 같은 능력의 선수를 묶어 하나의 컴포넌트로 생각할 것입니다.

 이후 '>' 관계에 따라 모든 컴포넌트를 정렬 할 수 있는지 여부를 판단해줍니다.

(1) 코드 29~35

 입력으로는 '=' , '>' 두 가지 관계가 들어옵니다.

    '=' 경우 : 하나의 컴포넌트로 묶어줍니다.

    '>' 경우 : 입력 당시는 각 선수 별 대소 관계입니다. 이를 이후 컴포넌트 별 대소 관계로 처리할 것입니다. 따라서 일단 대소 관계를 저장해 놓습니다. 

(2) 코드 36~49

 저장해 놓은 선수 별 대소 관계를 갖고 컴포넌트 별 대소 관계를 구성해줍니다.

 대소 관계는 set을 사용하여 컴포넌트 사이의 관계의 중복을 피해주었습니다.

 이 과정에서 각 컴포넌트는 자신보다 낮은 능력의 컴포넌트 수를 저장하여 위상정렬을 합니다.

(3) 코드 50~63

 과정(2) 에서 구성해 놓은 컴포넌트 간의 관계를 바탕으로 위상정렬을 실시합니다.

(4) 코드 64~67

 모든 컴포넌트가 정렬이 되는지 여부를 (혹은 모순된 관계가 있어서 정렬이 안되는지) 판단하여 답을 출력해줍니다.

	#include<bits/stdc++.h>
	using namespace std;
	typedef pair<int, int> pii;
	const int MAX = 50005;
	int N, M;
	// adj[x] : x를 root로하는 컴포넌트보다 큰 컴포넌트(의 root노드) 저장
	set<int> adj[MAX];
	// union-find
	int R[MAX];
	int find(int x) {
	if (R[x] < 0) return x;
	return R[x] = find(R[x]);
	}
	void merge(int x, int y) {
	int xRoot = find(x);
	int yRoot = find(y);
	if (xRoot != yRoot) R[xRoot] = yRoot;
	}
	set<int> arr; // 각 컴포넌트의 root 노드 저장
	int indegree[MAX]; // 각 컴포넌트에 들어오는 엣지 수
	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(R, -1, sizeof(R)); // 초기화
	cin >> N >> M;
	vector<pii> V; // 일단 관계 저장
	for (int i = 0; i < M; ++i) {
	int a, b;
	char c;
	cin >> a >> c >> b;
	if (c == '=') merge(a, b); // 하나의 컴포넌트로 묶기
	else V.push_back(pii(a, b)); // a > b
	}
	for (auto it : V) {// 관계를 컴포넌트별로 생각
	int a = it.first;
	int b = it.second;
	a = find(a); // 컴포넌트 별로 생각한다.
	b = find(b);
	// 컴포넌트 의 root들 저장
	arr.insert(a);
	arr.insert(b);
	// 컴포넌트 끼리 연결관계 최신화
	if (!adj[b].count(a)) { // 컴포넌트끼리 간선은 1개 ( 중복제거 )
	indegree[a]++; // a보다 능력 낮은 컴포넌트 수 ++
	adj[b].insert(a);
	}
	}
	// 위상정렬
	queue<int> Q;
	for (int it : arr)
	if (indegree[it] == 0) Q.push(it); // 능력 제일 낮은거로 시작
	int cnt = 0; // 정렬 된 컴포넌트의 수
	while (!Q.empty()) {
	int curr = Q.front();
	Q.pop();
	cnt++;
	for (auto it : adj[curr]) {
	indegree[it]--;
	if (indegree[it] == 0) Q.push(it);
	}
	}
	// 모든 컴포넌트의 위상이 맞는 경우 ( 모든 컴포넌트 개수만큼 cnt 가 세어진 경우 )
	if (cnt == arr.size()) cout << "consistent" << '\n';
	// 탈출 못한 컴포넌트 있는 경우
	else cout << "inconsistent" << '\n';
	return 0;
	}

view raw BOJ 13344.cpp hosted with ❤ by GitHub