위상 정렬 - Topological Sort )

안녕하세요 

오늘은 위상 정렬에 대해서 공부 해 보겠습니다.

 

위상 정렬에서 위상은 어떠한 사물이나 작업이 가지는 위치나 상태이고 그 위치들 간의 상호관계를 의미하고

어떤 사물이나 작업들이 어떻게 연결되고 어떤 순서로 배치되어 있는지에 대한 구조적 관계를 의미합니다.

 

위상 정렬은 순서에 제약이 있는 작업들을 올바른 순서로 배열 하는 방법입니다.

위상 정렬 알고리즘을 활용하려면 DAG(Directed Acycle Graph) 방향 비순환 그래프의 형태이여야 합니다.

그리고 정렬의 올바른 결과는 하나 이상일 수 있습니다.

 

일상 속의 아침 준비시간을 예로 들어보겠습니다.

 

아침 작업

• 양치하기
• 세수하기
• 머리 감기
• 아침 먹기
• 머리 말리기

제약사항

• 머리 감기는 머리 말리기 전 이어야 할 것
• 아침 먹기 다음 양치하기 전 이어야 할 것

 

만약 위와 같이 제약사항을 정해두었다고 생각해봅시다.

우리는 제약사항만을 지키고 나머지는 어떤 순서에 하든 상관이 없습니다.

아침먹기 -> 세수하기 -> 양치하기 이렇게 가도 되고

아침먹기 -> 양치하기 -> 세수하기 이렇게 가도 우린 제약을 지키고 있습니다.

 

 

위상 정렬을 구현하는 방법에는 2가지가 있습니다.

• 칸 알고리즘 
• DFS 알고리즘

 

방법 1: 칸의 알고리즘 방식

총 4명의 학생들이 각자 {1,2,3,4}의 번호로 이루어져 있습니다. 

 

예시 제약사항

• 4번은 2번보다 앞에 앉아야 해
• 3번은 1번보다 앞에 앉아야 해

위와 같은 제약을 가지고 있다면 어떻게 학생들을 줄을 세워야 할까요?

 

칸의 알고리즘은 진입 차수가 0인 것 부터 해결합니다.

여기서 진입 차수는 4번 뒤에 무조건 2번이 오는 것처럼

제약사항을 기준으로 무조건 뒤로 오게 정해진 것을 카운팅 한다고 보시면 됩니다.

• 1의 진입 차수는 1
• 2의 진입 차수는 1
• 3의 진입 차수는 0
• 4의 진입 차수는 0

처음엔 위와 같은 진입 차수로 이루어져 있고

우리는 0의 진입 차수부터 처리 할 것입니다.

 

3, 4가 진입 차수가 0이니 아무거나 먼저 처리를 해보겠습니다.

 

3을 먼저 젤 앞에 세우고

제약을 보면 우리는 이제 3을 맨 앞에 세웠으니

1은 이제 언제나 그 다음 어느 자리에 있던지 괜찮을 겁니다.

그것을 컴퓨터는 진입 차수로 판별을 합니다.

 

제약에 따른 3보다 무조건 뒤에 오는 수들은 진입 차수를 -1씩 해주면 됩니다.

컴퓨터는 아래와 같이 생각할 것 입니다.

"3이 먼저 나갔으니 이제 3이라는 하나의 숫자를 신경쓰지 않아도 되네?" 라고 말이죠

 

그렇게 된다면 1도 진입 차수가 0이 됩니다 1이 그 다음 와도 되고

4가 그 다음 와도 제약 사항에는 어긋나지 않습니다.

 

 

방법 2: Stack과 DFS의 역순

이 방법은 마지막에 있을 수 있는 수를 Stack에 먼저 넣겠다라고 생각하시면 편합니다.

 

그 다음 방법으로는 stack과 dfs의 역순을 활용하여 만들어 보겠습니다.

{A, B, C, D, E}를 위상 정렬 해 보겠습니다.

 

아래와 같은 제약 사항이 있습니다.

• A → B
• B→ C
• B → D
• D -> E

 

DFS는 한 번 파고들면 연결 되어있는 뿌리 끝까지 탐색을 우선시 하는 알고리즘입니다.

그리고 Stack를 사용해서 먼저 찾은 것을 stack에 먼저 넣도록 할 것 입니다.

 

A부터 탐색을 시작했다고 해봅시다.

 

A 다음 B 다음 C를 탐색 했다고 생각 해 봅시다.

C와 D는 같은 위치에 있으니 둘 중 어느 곳을 먼저 탐색해도 상관은 없습니다.

그럼 더 이상 갈 곳이 없으니 C를 Stack에 넣겠습니다.

 

그리고 나와서 D 다음 E

갈 곳이 없으니 E를 Stack에 넣겠습니다.

 

그리고 E를 나와서 D를 Stack에 넣겠습니다.

그리고 D를 나와서 B를 Stack에 넣겠습니다.

그리고 B를 나와서 A를 Stack에 넣겠습니다.

 

그럼 Stack에는 현재 {C, E, D, B, A}가 들어가 있습니다.

Stack은 가장 먼저 들어간 것이 나중에 나오는 성질을 가지고 있습니다.

 

한 번 POP을 해보면 {A, B, D, E, C}의 형태로 리버스된 것을 알 수 있습니다.

우리가 구한 이 리스트는 제약사항을 만족하고 있는 것 같습니다.