백준 3665 최종 순위

위상 정렬을 활용한다. graph와 indegree배열, queue를 사용한다.

문제의 예제와 같이 1등부터 시작해서 5등까지 팀이 5 - 4 - 3 - 2 - 1 인 경우,

그래프를 5 -> 4 -> 3 -> 2 -> 1 형태로 그리는 것이 아니라

5 -> 4 /  5, 4 -> 3 / 5, 4, 3 -> 2 / 5, 4, 3, 2 -> 1 처럼 각 정점에 도달하기 위해 거쳐야 하는 정점들을 모두 연결하게 그려서 각 정점이 서로 연결되어 있게(indegree도 그에 맞게 ++해주어야 한다) 한 후, 위상정렬을 진행한다.

indegree가 0인 것을 queue에 넣고, graph에 따라서 탐색하면서 다음 것의 indegree를 -1해주고 indegree가 0이면 queue에 넣어주는 식으로 진행한다.

만약 indegree가 0인 것이 없다면 모순이 있어 순위를 정할 수 없는 경우이고,

indegree가 0인 것이 동시에 여러개가 생긴다면 확실한 순위를 찾을 수 없는 경우로 볼 수 있다.

-----------------------

직접 구현해보니, 상대적 순위가 바뀌었다는 정보에 대해서 그래프를 수정해주는 것이 문제이다. 둘 중 누가 앞서 있는지도 알아야 하고, 그래프에 연결된 점을 일일이 다 보면서 찾아야 하는데 m이 25000이라... 그래프에 연결된 점이 최대 500개정도 된다고 하면 12,500,000번을 봐야 하는데,  테스트 케이스가 최대 100개라 시간초과가 날 위험이 있다.

그래서 vector를 사용하는 인접리스트 대신에 인접행렬을 써볼까한다. 일단 500 * 500이라 메모리는 문제없고, 인접행렬을 사용하면 일일이 다 볼 필요가 없고, 둘 중 누가 앞서 있는지도 쉽게 파악 가능하다.

아 참고로 인접리스트를 쓴다면, 소팅하여 이분탐색을 이용하는 방법도 있을 것이다.

---------------------------

계속 틀려서... 고민하다가 겨우 원인을 알아냈다.

바로 순위를 정할 수 없는 경우를 알아내는 부분에서 문제가 있었다. 나는 indegree가 0인 것이 없는지를 맨 처음에만 판단했다. indegree가 0인 것이 없으면 사이클이 생기는데, 사이클이 처음부터 생기지 않을 수도 있다. 일단 처음에는 indegree가 0인 것이 존재해서 queue에 들어가고, 계속 진행하다가 indegree가 0인 것이 없는 상황이 올 수가 있는 것이다... 

반례)

input

1

4

1 2 3 4

2

3 4

2 3

output으로 "IMPOSSIBLE"이 나아야 하는데, 나의 틀린 코드로 돌리면 "?"가 나왔다.

그래서 그 경우를 처리했더니 AC를 받았다... 

** 참고) 그리고 문제 관련 질문을 보던 중 확실한 순위를 찾을 수 없는 경우는 나올 수 없다는 답변이 있었는데, 실제로 그 답변을 잘 이해하진 못했고, 나도 정확히 증명은 못하겠지만 실제 예제나 반례를 만들어 보면서 확실한 순위를 찾을 수 없는, indegree가 0인 것이 동시에 여러개 생기는 경우를 만들지 못했었다.