[BOJ][3665] 최종 순위

문제 : https://www.acmicpc.net/problem/3665

---

위상정렬 문제다.

등수가 3등인 사람은 1, 2등이 정해지는 경우 3등이 정해진다.

이를 그래프로 나타내면 위와 같다.

1등은 앞에 아무도 없는 경우 1등이다.

2등은 1등이 정해져서 화살표가 없어지면 2등 앞의 등수가 아무도 없게되고 2등이 정해진다.

3등도 마찬가지로 1, 2등이 정해지면 3등이 정해진다.

m개 등수가 바뀌는 쌍이 주어지면 2개 화살표를 반대로 바꾼다.

만약 m이 2이고 (1,2), (2,3)이 입력값으로 주어지면 위 그림과 같이 화살표가 바뀐다.

이때, 1, 2, 3 사이에는 싸이클이 생겨서 1등을 정할 수 없게 되서 IMPOSSIBLE을 출력한다.

모든 등수 뿐만 아니라 2개 이상의 등수 사이에 위와 같이 싸이클이 발생하면 등수를 명확히 구할 수 없으므로 IMPOSSIBLE을 출력한다.

m개의 등수가 변경된 상태까지 적용한 그래프를 구한 뒤, 위상정렬을 적용한다.

즉, 어떤 이전에 필요한 화살표가 물려있지 않는 팀의 경우 정답 배열에 차례대로 넣는다.

이 때, 화살표가 0개인 팀의 개수가 0개라면 탐색이 끝난 경우이고, 1개라면 위상정렬을 계속해야 하는 경우, 2개 이상이라면 확실한 순위를 찾을 수 없으므로 ?를 출력한다.

화살표가 0개인 팀이 0개라면 탐색이 끝나서 정답이 확정되게 된다. 그런데 정답 배열에 n개가 없다면 앞에서 말한 싸이클이 존재한다는 뜻이므로 "IMPOSSIBLE"을 출력한다.

구현은 연결리스트, 배열로 구현할 수 있는데 이번엔 배열로 구현했다. 따라서 시간복잡도는 O(N^2).

---

소스코드 : https://gist.github.com/fpdjsns/f0c8f37f90f071262b041b5f7db7b3af