알고리즘 - 위상 정렬

위상 정렬이란,  선후 관계가 존재하는 대상의 순서를 정렬하는 알고리즘이다.

게임에서 스킬 트리를 생각해보자

설명을 보면, 다크 사이트를 10레벨 이상 배워야만 어드밴스드 다크 사이트를 배울 수 있다고 적혀있는 것을 볼 수 있다.

즉, 스킬을 배우는 순서대로 정렬한다면 무조건 다크사이트가 앞에 올 수 밖에 없는 것이다.

 

이처럼, 어떤 작업을 완료하기 위해 선행해야 하는 작업이 있는 상황에서 작업의 순서를 정렬하는 알고리즘을 위상 정렬이라고 한다.

위의 그래프에서 화살표를 선행관계라고 해보자.

1번을 완료해야만, 2,3번을 작업할 수 있다는 뜻이다.

 

즉, 위의 표에서 작업의 실행 순서대로 정렬한다면 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 로 정렬할 수 있을 것이다.

하지만, 1 -> 3 -> 2 -> 4 -> 5 -> 7 -> 8 -> 6 으로 정렬할 수도 있다.

 

선행 작업이 모두 완료된 작업들 사이에서는 선행, 후행이 존재하지 않으므로 정렬 결과가 다양하게 나올 수 있다는 것을 염두에 두자. 

 

그렇다면, 위상 정렬은 어떤 과정으로 이루어질까?

먼저, 진입 차수라는 개념이 나온다.

 

진입 차수란, 해당 작업을 실행하기 위해 선행되어야 하는 작업의 개수를 의미한다.

 

위의 그래프에서 보자.

2, 3번 작업을 실행하기 위해선 1번 작업을 먼저 실행해야 한다.

그러므로, 2,3의 진입차수는 1이 된다.

 

반면, 4번 작업을 실행하기 위해선 (2, 3) 두 개의 작업을 실행해야 한다.

이 때, 4번 작업의 진입 차수는 2라고 할 수 있다. (1까지 포함해서 3개가 아니냐? 라고 할 수 있지만, 바로 앞에서 선행되어야 하는 작업에 대해서만 계산한다.)

 

진입차수 배열을 만들어서, 정리해보자.

각 작업에 대한 진입차수는 위와 같이 정리될 것이다.

배열 값을 보면, 1번만 0인 것을 볼 수 있다.

 

모든 작업이 실행되려면, 가장 먼저 실행되어야 하는 작업이 존재할 것이다.

그리고 해당 작업에 대해서는 선행 작업이 없어야 한다. (당연히 모든 작업에 대해 선행작업이 존재한다면, 무한 순환이 발생하면서 작업의 순서를 매길 수가 없게 된다. )

 

그러므로, 진입차수가 0인 작업이 무조건 가장 먼저 실행되는 작업이 된다는 것이다.

작업 순서 배열도 하나 만들어서, 0번을 가장 앞에 삽입하자.

 

 

0번 작업을 시작으로, 작업을 시작해보자.

 

1번 작업이 끝났다면, 이제 1번 작업을 선행으로 하는 작업들의 진입 차수를 1씩 내려보자.

하나의 작업이 끝났다면, 해당 작업을 선행으로 하는 작업들의 진입차수를 1씩 깎으며, 다음 작업을 탐색할 것이다.

 

위와 같이 진입차수 배열이 갱신되었다.

보면, 2와 3번 작업에 대해 진입차수가 0이 된 것을 볼 수 있다.

즉, 새롭게 진입 차수가 0이 된 작업들은 모든 선행작업이 완료되었다는 뜻이다.

 

2번과 3번 작업에 대해서도, 후행 작업의 진입차수를 깎으며 배열을 갱신할 것이다.

그 이전에, 2번과 3번 작업을 작업 순서 배열에 삽입해주자.

 

다음은 진입차수 배열을 갱신해보자.

2번 작업에 대해 갱신을 하면 위와 같아진다.

 

3번 작업에 대해서도 갱신하면, 위와 같이 4번 작업의 진입차수가 0이 된다.

이제, 작업 순서 배열에 4번을 삽입해주자.

 

이 과정을 계속 반복하면, 아래와 같이 작업 순서 배열을 완성할 수 된다.

 

 

이처럼, 진입차수가 0이되는 작업을 현재 실행해야 하는 작업이라 가정한 뒤, 진입차수를 계속 갱신하며 0이 되는 작업을 순서대로 배열에 삽입해주면 위상 정렬이 완료된다.

 

이해를 더하기 위해, 코드를 보며 이해하는 것도 좋다.

아래는 위상정렬을 활용한 예제 문제이다.

 

백준 14567 - 선수 과목 (C++) (tistory.com)

백준 14567 - 선수 과목 (C++)