3665
-
[백준] 3665번 최종 순위 (by Python)Programming/Algorithm 2021. 3. 14. 02:25
문제 www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 위상 정렬(Topology Sort)를 사용하는 문제이다. 주어진 올해 순위를 순위가 낮은 팀이 높은 팀을 가리키는 유향 그래프로 나타내었다. 원래는 위상 정렬에 쓰이는 그래프는 인접 리스트로 구현하였는데, 이번에는 방향성이 유동적이므로 이를 잘 다루기 위해 인접 행렬로 구현했다. 바뀐 순위들에 대해서 edge의 방향을 바꾸어주고 이에 대해 위상 정렬을 시행해주면 된다. 다만 주어지는 정보에 ..