[BOJ] 3665 최종 순위 (C/C++)

3665번: 최종 순위

문제

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.

올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.

입력

첫째 줄에는 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)
• n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다.
• 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)
• 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.

출력

각 테스트 케이스에 대해서 다음을 출력한다.

• n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

---

마지막으로 위상 정렬 문제를 푼지 2주가 넘은 것 같아서 한번 더 풀어봤다. 어느새 백준 단계별로 풀어보기에서 위상 정렬 파트 4문제를 다 풀었다. 

 

문제 조건에서 원래 순위가 주어지고 바뀐 순위가 들어온다. 바뀐 순위를 정확히 알아내거나, 정확히 알아내지 못하는 경우와 불가능한 경우를 모두 판정하는 문제였다. 이번 문제는 단순한 위상 정렬 문제에서 조금 꼬아져있다고 느꼈다. 원래는 순서에서 가장 먼저 처리해야 하는 것부터 하나씩 해결해나가면서 이 다음에 처리할 수 있는 정점을 찾았는데, 이 문제는 1등부터 처리해야했다. 다 풀고나니 결국은 같은 말이라는 것을 이해했지만 문제를 처음 봤을 때 직관적으로 와닿지 않아서 문제를 이해하는 꽤 시간을 써야했다. 

 

그리고 평소에 풀던 위상 정렬 문제보다 간선을 많이 저장해야 했다. 처음에 들어오는 작년 순위를 보고 필요한 간선을 모두 연결해줬다. 그 이후에 원래 간선이 있는 경우, 없는 경우를 나눠서 간선을 뒤집거나 새로운 간선을 만들었다.  

 

중간에 큐에 원소가 두개 이상이 들어있는 경우엔 선택할 수 있는 간선이 두개 이상이었다는 말이므로 둘 중 어느 간선을 먼저 택해야할지 우선순위를 결정할 수 없는 상태이다. 따라서 최종 순위가 어떨지 확정할 수 없다. 

 

그리고 마지막에 큐의 사이즈가 N이 아닌 경우엔 최종 순위를 결정하는데에 실패했으므로 불가능하다고 출력한다.  아마 그래프가 연결 그래프가 아니거나 그래프에 사이클이 생기면 순위 결정에 실패하는 것 같다.

 

 

후기)

내 멋대로 인덱스를 0부터 했다가 문제에서는 1부터 들어온다는 것을 디버깅을 하다가 찾았다. 평소에는 잘 읽었던 것 같은데 왜 하필 오늘은 안 읽었을까... 아니 재수가 없는게 아니라 실력이 없는거지^^ 문제를 잘 읽자^^