[Algorithm] 위상 정렬 - C

https://m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-sort

[알고리즘] 그림으로 알아보는 위상 정렬(Topology sort)

위 블로그를 참고하였습니다.

---

> 위상 정렬이란?

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
위상 정렬을 사용하면 기존에 해줘야 하는 작업들을 순서대로 정렬할 수 있으며, 해당 그래프가 위상 정렬을 사용할 수 있는 그래프인지까지 알 수 있다.
- https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

> 그럼 어떻게 만들 수 있는가?

queue, 또는 stack을 이용하여 구현할 수 있다고 한다.

일단 여기서 필자는 queue를 이용하여 구현을 했다.

백준 1005번 ACM Craft (https://www.acmicpc.net/problem/1005) 를 풀 때 사용했다.

 

> 알고리즘 순서 (queue를 이용한 방법)

1. 먼저 노드에 오는 간선 개수가 0인 노드들은 큐에 추가한다.
2. 큐에서 노드를 하나 빼서 그 노드가 가리키는 간선들을 제거한다.
3. 큐에서 빠진 노드를 리스트에 추가한다.
4. 다시 노드에 오는 간선 개수가 0인 노드들을 큐에 추가한다.
5. 2, 3을 큐가 비워질 때까지 반복한다.
6. 큐가 비워졌을 때 만약 모든 노드가 큐에서 나오지 않았다면(리스트 요소 개수 != 총 노드 개수), 그 그래프는 위상 정렬이 불가능한 그래프(loop가 존재)이다.
7. 위상 정렬이 성공이라면, 위에서 빠진 노드들을 추가해 줬던 리스트가 위상 정렬이 된 리스트이다.

> 알고리즘 (stack을 이용한 방법)

1. 한 노드를 선택해 dfs를 시행한다.
2. 노드

> 결론

시간 복잡도가 O(V+E)라서 상당히 빠른 정렬이라고 한다. (V는 노드의 개수, E는 간선의 개수이다)

1005번은 아직 도전 중이나, 처음에 사용했던 방식인 map과 queue를 이용한 탑-다운 dp보다는 나은 것 같다.