위상정렬

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 위상정렬이란

사이클이 없어 순환하지 않는 방향 그래프의 모든 노드를 방향성에 어긋나지 않도록 순서대로 나열하는 정렬이다. 만일 선수과목을 고려한 수강 과목 순서를 결정하는 문제와 같이 선후관계를  지켜야하는 알고리즘 문제가 있다면 위상정렬을 수행해 문제를 해결할 수 있다. 

위상정렬에선 여러가지 답이 존재할 수 있는데 이는 작동과정에서 설명할 큐에 들어가는 원소가 두개 이상일 때 발생한다, 

만일 모든 원소를 방문하기 전에 검색되어야 하는 노드들이 순서대로 들어가 있는 큐가 빈다면 이는 그래프에 사이클이 존재함을 의미한다. 사이클이 존재하는 그래프에선 위상정렬을 수행할 수 없다. 

> 시간복잡도: 차례대로 모든 노드를 확인하며 간선을 제거해야하기 때문에 노드의 개수를 V, 간선의 개수를 E라고 하면 O(V+E)의 시간복잡도를 가진다. 

 

 

 

▶ 용어 정의

진입차수 Indegree: 특정 노드로 들어오는 간선 개수

진출차수 Outdegree: 특정 노드에서 나가는 간선 개수

 

 

 

▶ 동작과정

들어온 순서대로 나가는 자료구조인 큐를 활용하여 위상정렬을 구현할 수 있다.

 

step1. 진입차수가 0인, 즉 노드로 들어오는 간선 개수가 하나도 없는 노드를 큐에 넣는다. 

step2. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 제거한다. 

step3. step2에서 간선을 제거하다보면 진입차수가 0인 노드가 추가적으로 나온다. 이 노드들을 큐에 넣어준다. 

step4. 큐에 쌓인 노드들의 순서가 위상정렬을 수행한 그래프이다. 

 

 

 

▷ 예시

다음과 같은 그래프에 대해서 모든 노드의 선후관계를 지키면서 모두 이어질 수 있도록 노드를 정렬해보자.

1. 먼저 진입차수가 0인 노드1을 큐에 넣는다 -> [1]

2. 1번 노드에서 나가는 간선을 제거한다. ->[]

3. 2번 노드의 진입차수가 0이 되므로 노드 2를 큐에 넣는다. -> [2]

4. 2에서 나가는 간선을 제거한다. ->[]

5. 3의 진입차수가 0이 되므로 노드 3을 큐에 넣는다 -> [3]

6. 3에서 나가는 간선을 제거한다. ->[]

7. 노드 4의 진입차수가 0이 되므로 큐에 넣어준다, -> [4]

8. 큐에서 맨 앞 요소인 4를 뽑는다. 노드 4에서 나가는 노드가 없다. ->[]

9. 큐가 비었으므로 알고리즘을 종료한다.

10. 큐에 들어온 순서인 1,2,3,4가 위상정렬을 수행한 결과이다. 

 

 

 

▷ 구현

위의 예시를 위상정렬 알고리즘으로 구현해보자. 

먼저 노드 개수와 간선개수, 그리고 간선정보를 입력한다. 

위상정렬 알고리즘을 구현하여 결과를 출력한다. 

예시에서 보았듯이 그래프를 위상정렬한 결과가 올바르게 출력됨을 볼 수 있다.