3665 (1) 썸네일형 리스트형 [C++/3665] 최종 순위 - using 위상 정렬 (topology sort) 문제 아이디어: 위상 정렬 문제에서는 "순위"를 나열해야 하기 때문에 방향 그래프라는 것을 쉽게 알 수 있다. 이를 순위에 맞게 나열하는 것은 방향 그래프를 정렬하는 것과 같으므로 위상 정렬을 사용할 수 있다. 이때 사이클이 없는 위상 정렬은 항상 노드가 N개 일때 queue를 N번 돌기 때문에, 사이클이 생긴다면 N보다 작은 횟수로 종료하게 된다. 왜냐하면 진입 차수가 0이 되는 노드가 없어서 더 이상 탐색을 진행할 수 없기 때문이다. 따라서 이 경우 쉽게 "IMPOSSIBLE" 인 경우를 알 수 있다. 데이터의 일관성이 없는 경우 "?"를 출력하라고 하였는데 이는 같은 등수인 노드가 여러개인 경우이다. 이 오류는 queue에 들어간 node의 갯수가 몇개인지에 따라 알 수 있다. 즉 2개 이상의 no.. 이전 1 다음
