백준 3665번 최종순위

문제

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

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

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

문제풀이

사용한 알고리즘: 위상정렬

(1) 생각

 문제에서 작년 순위를 주고, 순위가 바뀐 모든 팀의 정보를 주므로,
 확실한 순위를 모르는 경우 ('?' 인 경우) 는 없습니다.

(2) 코드 6~7

 'adj[a][b] = true : b팀 앞에 a팀이 와야함'
 'indegree[x] = x 앞에 와야 하는 팀개수' 로 설정하였습니다.

(3) 코드 20~25

 작년 팀 간의 순위를 저장하여줍니다. 이때 indegree를 같이 세줍니다.

(4) 코드 28~46

 순위가 바뀐 팀의 상태를 업데이트 해줍니다. 이때 역시 indegree를 같이 세줍니다.

(5) 코드 53~65

 indegree=0 인 팀부터 위상정렬을 구현해줍니다. 앞서 말했듯이 확실한 순위를 모르는 경우 즉, 두 팀의 indegree가 동시에 0인 경우는 없다는 믿음을 갖고 구현해줍니다.

(6) 코드 66~74

 구한 순위가 총 N개의 팀이면 답을 찾은 것입니다. 아니라면 일관성이 없는 잘못된 정보입니다.