최종순위
동빈북 풀이
- 핵심1. 순위를 나타내는 그래프를 어떻게 방향 그래프로 나타낼 것인가?
- 순위의 상대성을 표현해야 하기 때문에 ex. 1 2 3 4 5 라고 순차적으로 등수라고 했을 때 단순히 리스트로 1 2 3 4 5 하면 안된다. 왜냐면 그 다음에 제공되는 정보가 1 > 2 3 > 5 와 같이 바로 앞뒤로 있는 순위 외에도 상대적인 순위격차가 필요하기 때문에?
- 위상정렬을 사용했을 때 순위대로 나오게 그래프를 만들 수 있다. 예를 들어 예시에서 5 4 3 2 1 (앞에서부터 1등) 이라고 했을 때 자신보다 낮은 친구를 가리키게 한다. 아래와 같이
그러면 1등이 진입차수 0, 2등이 진입차수 1 이렇게 되면서 위상정렬을 수행했을 때 5 -> 4 -> 3 -> 2- > 1 이렇게 가리키게 된다. 
- 여기서 해당 순위가 바뀌게 되면 간선의 방향만 바꾸면 된다. 예를들어 여기서 2팀, 4팀의 순위가 바뀌고 팀 3, 4가 바뀐다고 하면은 위의 그림과 같이 된다.
- 이렇게 순위를 바꾸면서 위상정렬을 수행하면서 사이클이 발생하는지, 결과가 여러 가지인지 확인하면 된다.
- 일반적인 위상 정렬의 경우 정확히 n개의 노드가 큐에서 출력이 된다. n개의 노드가 나오기 전에 큐가 비면 사이클이 발생한 것으로 이해한다.
- 특정 시점에 노드가 2개 이상 들어갈 때는 가능한 정렬 결과가 여러가지라는 말
위상정렬
- 위상정렬에서 사이클이 문제되는 이유
- 위상정렬에서 탐색 순서가 여러 개 나올 수 있다.
- 일반적인 위상 정렬의 경우 정확히 n개의 노드가 큐에서 출력이 된다. n개의 노드가 나오기 전에 큐가 비면 사이클이 발생한 것으로 이해한다.
- 특정 시점에 노드가 2개 이상 들어갈 때는 가능한 정렬 결과가 여러가지라는 말
spring, java학습