Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
3665번: 최종 순위
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에
www.acmicpc.net
풀이
solved.ac 난이도: Gold 1
[백준] 알고스팟어(2848)과 비슷한 위상 정렬 문제였다.
처음에는 저번 대회의 순위를 저장하여 등수가 바뀐 쌍에서 저번 대회에 더 순위가 높았던 팀이 이번에는 더 낮은 팀으로 바뀌게 설정하였다.(간선을 이번 대회에서 높은 팀 -> 낮은 팀으로)
이렇게 바뀐 쌍에서만 방향 그래프의 연결을 진행하였더니 아래와 같은 결과가 나왔다.
예제의 입력
저번 대회 등수: 5 4 3 2 1
바뀐 쌍: (2 4) (3 4)
이번 대회의 등수의 그래프는 다음과 같이 나타난다.
이런 경우 들어오는 간선의 수 indegree가 0인 노드가 2와 3 두 개이므로 여러 개의 순위가 나올 수 있다.
하지만 저번 대회에서 3은 2보다 등수가 높았고 이번 대회에서 순서가 바뀌지 않았으므로 3은 2보다 등수가 높다.
이러한 그래프 표현까지 나타내기 위해 저번 대회의 등수를 토대로 미리 등수 관계 간선을 연결해주자.
(1등 -> 2등), (1등 -> 3등), (1등 -> 4등), (1등 -> 5등)...
(2등 -> 3등), (2등 -> 4등), (2등 -> 5등), ...
(3등 -> 4등), (3등 -> 5등), ...
.
.
.
(n-1등 -> n등)
여기서 새로 등수가 변한 쌍만 관계를 역전해주고 indegree를 변경해주면 모든 팀들의 등수 순서가 연결되어 정상적으로 위상 정렬이 가능해진다.
이번 문제에서 사용한 큐를 이용한 위상 정렬에 대해서는 동일하 코드로 해결한
[백준] 알고스팟어(2848) 을 참고하자.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.11266 - 단절점 (C++, Articulation point ) (0) | 2021.03.14 |
|---|---|
| [백준] No.18250 - 철도 여행 (C++, 오일러 경로) (0) | 2021.03.13 |
| [백준] No.2637 - 장난감 조립 (C++) (0) | 2021.03.08 |
| [백준] No.2848 - 알고스팟어 (C++, 위상 정렬) (0) | 2021.03.07 |
| [백준] No.9466 - 텀 프로젝트 (C++, DFS) (0) | 2021.03.06 |