백준 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

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