ssh9199   6달 전

위상 정렬을 사용했습니다.

진입 차수를 탐색할 때 priority_queue를 이용하여 진입차수가 가장 낮은 node의 index를 뽑고, 해당 index의 node에 연결된 next node들의 진입차수를 1씩 감소시켜줍니다.

이 때 해당 index의 node의 진입차수가 0보다 크면 사이클이 발생한 것으로 간주할 수 있으므로 바로 0을 출력 후 리턴합니다

제가 놓친 부분이 있을까요? ㅠㅜ

* CompareNodeInCnt에서 바로 // return nodes[n1].inCnt > nodes[n2].inCnt // 만 해주어도 되지만, 순서만 만족하면 어떻게 해도 상관 없다길래 작은것부터 출력되도록 했습니다.

(추가) pq를 사용하지 않고 일반 queue를 사용해서 AC 받았습니다. 일반 queue의 경우에는 현재 node와 연결된 next node들의 진입차수만 확인하고 pq의 경우에는 모든 node들의 진입차수를 확인하는데, 이 때 생긴 순서의 차이로 인해 오답이 난 것 같습니다.

가령, 다음 데이터에 대해서

5 5
2 1 2
2 1 3
2 1 4
2 2 5
2 3 5

pq의 경우에는 답이 1 2 3 5 4가 나올 수 있지만, 일반 queue를 사용한 경우에는 1 2 3 4 5가 됩니다.

즉, pq는 1을 탐색 후 2 3을 탐색했다면 5를 탐색할 수 있는 여건이 되지만,

일반 queue는 1을 탐색 후 2 3 4까지 전부 탐색하지 않으면 2 3을 탐색할 때 이미 5의 진입차수가 0이 되었음에도 5를 탐색할 수 없습니다.

문제에서 "답이 여러 개인 경우 아무거나 출력한다"라고 언급되어 있는데, "queue를 사용하여 탐색한 경우의 아무거나 출력한 것"만 정답 데이터에 올라와 있는 건 아닐까 추측해 봅니다. 즉 위의 데이터에 대해서는 [1 (2 3 4) 5], [1 (2 4 3) 5], [1 (3 2 4) 5], [1 (3 4 2) 5], [1 (4 2 3) 5], [1 (4 3 2) 5] 만 정답 데이터로 간주하고 채점한 것 같다는 말입니다.

만약 위 추측이 맞다면, 데이터를 추가해주시거나, 문제의 표현을 바꿔주셔야 할 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.