1. 정의
위상 정렬이란, 사이클이 없는 방향 그래프에서 정점을 정렬하는 알고리즘이다.
(1) 사전 지식
A. 진입 차수란?
방향 그래프에서 본인을 향해 있는 간선의 개수가 바로 진입 차수이다.
반대로 본인에서 나가는 간선의 개수는 진출 차수라고 부른다.
위의 사진에서 진입차수는 3이고, 진출 차수는 2라고 할 수 있다.
B. 정점끼리의 관계에서 선행된다와 후행된다의 차이
기준 정점에서 볼 때, 자신에게 진입하는 간선을 가진 정점을 선행하는 정점, 자신이 진출하는 정점을 후행하는 정점으로 볼 수 있다.
(2) 정렬의 기준은?
정렬의 기준은 선행되는 정점의 개수이다. 즉 선행되는 정점이 많을수록 우선순위가 낮다. 이를 위해서는 위에서 설명했듯이 (1) 사이클이 없고, (2) 방향 그래프임이 전제되어야 한다.
다음의 그림을 통해, 왜 그런 전제들이 존재해야 하는지 살펴보자.
A. 그래프가 사이클인 경우
1번에서 시작해서 5번까지 갔더니, 맨 마지막 정점이라 생각했던 5번이 다시 1번의 선행이 된다. 즉 모든 정점이 서로의 선행되는 작업이 되므로 순서의 의미가 없어지기 때문에 위상 정렬을 활용하지 못한다.
B. 무방향 그래프인 경우
하나의 간선이 진입 차수도 되고 진출 차수도 되는 무방향 그래프라고 하면, 이 그래프 또한, 선행되는 작업이 무엇인지 알 수 없기 때문에, 위상정렬을 활용할 수 없다.
C. 사이클 없는 방향 그래프
위상정렬의 정렬기준은 '선행되는 작업이 많을수록 우선순위가 낮다' 고 하였다. 그 기준에서 보면 1이 제일 우선순위가 높고, 5가 제일 작음을 알 수 있다. 따라서 1부터 시작해서 5로 끝나는 정점 정렬이 가능해진다.
다만 위상정렬로 나올 수 있는 정렬의 가짓수는 2개 이상일 수 있다. 위의 문제에서도 볼 수 있듯이, 정점 2와 3은 서로 선행되어야 하는 정점의 개수와 후행되어야할 정점의 개수가 같다. 따라서 정렬 결과는 1 ➜2➜3➜4➜5 또는 1➜3➜2➜4➜5 둘 다 가능하다.
(3) 관련 문제
"선행되어야할 작업이 있다면, 그 순서대로 나열해라" 와 같은 유형의 문제들
- 교과목 선수 과목 순서 정하기
- 프로젝트에서 어떤 작업을 먼저 해야 다음 작업이 가능한지 순서 정하기 등
2. 구현
(1) 그림으로 직관적으로 이해하기
다음 2가지만 기억한 채로 구체적인 진행 과정을 보자
- 특정 정점의 진입차수가 0이라는 것은 가장 선행되는 정점이라는 뜻이다.
- 매번 가장 선행되는 정점을 방문해서 그것의 진출 간선을 진입 간선으로 가지는 정점의 진입 차수 개수를 1 줄여준다.
이는 진입 차수가 0이 되는 정점을 새로 만들어주기 위함이다.
0. index = 정점 번호, value = 해당 정점의 진입 차수인 진입차수 배열을 만든다.
위와 같이, 입력값으로 인접 리스트를 만들 때 같이 만들면 된다. 이때, 정점이 정렬된 순서를 삽입되는 정답 큐도 같이 만들자.
1. 진입차수가 0인 정점을 찾아서, 정답 큐에 넣는다.
'진입 차수가 0이다 '의 뜻은 현 시점에서 가장 선행되는 작업이라는 뜻이다.
2. 현 방문 정점의 진출 차수를 하나씩 없앤다.
1번의 진출 차수를 다 없애버리면, 2와 3의 진입 차수는 0이 된다.
이제 이후 가장 선행되는 정점을 찾아서 1번과 2번을 반복해주면 되는데, 현 시점에서 가장 선행되는 정점이 2와 3으로 두 개 이다.
위에서도 설명 했듯이, 위상정렬로 나올 수 있는 정렬의 경우의 수는 1가지를 넘을 수 있다. 이건 문제에서 주어진 추가 조건에 따라 정하도록 하자.
3. 1번과 2번을 반복한다.
(2) 구현 원리
-
- 인접 리스트 만들 떄, 진입 차수 배열을 만든다.
- 밑의 (1) ~ (2)을 모든 정점을 방문할 때까지 반복한다. (정답 큐에 저장되었다. == 방문 했다.)
- (1) 현 시점에 진입차수가 0인 정점 (가장 선행되는 작업)을 고르고, 이를 정답 큐에 저장한다.
- (2) 해당 정점의 진출 간선을 확인해 그것을 진입 간선으로 가지는 정점의 배열 값을 1 내린다.
해당 구현을 위해서는 BFS의 원리가 자주 이용된다. 다음과 같이 작동한다.
- 최초에 진입 차수가 0인 녀석들을 전부 큐에 저장
- 이후 BFS 돌면서, 진입 차수 배열 최신화.
- 만약 특정 정점의 진입 차수가 0이 되면 그것도 큐에 넣는다.
- 모든 정점을 방문했을 때, BFS 종료
