위상정렬 (Topological Sorting) (백준 3665 최종순위)

순위를 찾거나, 선수과목(prerequiste) 구하기등 순서가 중요할 때 사용할 수 있다.

백준 3665 최종순위는 위상정렬을 사용해 풀 수 있다.

3665번: 최종 순위

위상정렬이란?

• 방향 그래프에 존재하는 정점들의 순서를 구하는 알고리즘이다.

특징

• 하나의 방향 그래프에는 여러 위상 정렬이 가능하다.
• 순서를 구할 때 선행조건이 지켜져야 한다. (A를 하기 위해 B가 선행되야 한다 등의 조건들)
• 그러나 최종 순위처럼 한 가지 결과를 원할 때는 조건을 걸어서 2개 이상의 결과가 나오는 것을 차단해야한다.
  • 진입 차수를 활용해야 한다.

 

출처 : https://velog.io/@gimtommang11/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EA%B7%B8%EB%9E%98%ED%94%84

진입 차수란,
한 노드를 가리키는 간선의 개수를 말한다. 위 그림에서 A의 진입 차수는 0이고 B의 진입 차수는 1이다.  
A가 B를 가리키면 B는 A의 선행 조건이다. 즉, A가 되기 위해서는 반드시 B가 선행되어야 한다.

순위를 나타내는 방향 그래프라면 A가 1위 B가 2위인 상황이다. 이것은 위상 순서 라고한다.

위상 정렬의 과정

• 2차원 배열이나 리스트 등에 간선 정보를 담는다.
• 간선 정보에 맞게 진입 차수도 (배열 등에) 저장한다.
  • 만약 A, B, C 순서대로 1, 2, 3등 이라는 정보가 있을 때, A->B, A->C, B->C 라는 간선이 존재한다.
  • matrix[0][1] = 1; matrix[0][2] = 1; matrix[1][2] = 1; 이런 식으로 간선 정보를 저장하고,
  • B를 향하는 간선은 A 하나, C를 향하는 간선은 A와 B 둘이므로 진입차수 A-0, B-1, C-2가 된다.
• 진입 차수가 0인 정점을 찾아서 큐에 저장한다.
  • 진입 차수를 담은 큐의 사이즈가 곧 결과의 개수다. 즉, 사이즈가 0이면 위상 정렬이 불가능하므로 중단한다.
  • 진입 차수가 0인 노드를 담은 큐의 사이즈가 2이상이 되면 2개 이상의 결과가 나오게 된다. 최종 순위는 1가지 결과이므로 2이상이면 예외처리가 필요하다.
• 큐에 저장된 노드들을 꺼낸다. (순위등 필요한 작업을 수행한다.)
• 꺼낸 노드와 연결된 간선들을 지우고, 해당되는 노드들의 진입 차수도 줄인다.
• 위 작업을 반복한다.

참고

gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html#:~:text=%EB%82%98%EC%97%B4%ED%95%98%EB%8A%94%20%EA%B2%83-,%EC%9C%84%EC%83%81%20%EC%A0%95%EB%A0%AC(Topological%20Sort)%EC%9D%98%20%ED%8A%B9%EC%A7%95,(Topological%20Order)%EB%9D%BC%20%ED%95%9C%EB%8B%A4.

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog