위상정렬(백준 알고리즘 14567번)

♣ 위상정렬의 정의

위상정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 아래와 같은 비순환 방향 그래프(DAG: Directed Acyclic Graph) 에서 가능하다. 

 

위의 DAG에서 노드들을 방향성에 거스르지 않는 순서대로 나열하면 아래와 같다. (위상정렬 결과)

 

예시1

 

예시2

 

사이클은 노드 사이에 선수관계를 알 수 없는 그래프를 의미한다. 사이클이 있는 방향 그래프에서는 어느 노드가 선순위에 있는지 알 수 없기 때문에 위상정렬이 불가능하다. 

 

 

♣ 진입차수와 진출차수

진입차수(Indegree)는 노드로 들어오는 간선의 수를 의미한다. 

진출차수(Outdegree)는 노드에서 나가는 간선의 수를 의미한다. 

위 그래프에서 노드 4를 예로 들면 진입차수가 1개(3 => 4), 전출차수가 2개(4 =>1, 4=>2)이다.  

 

 

♣ BFS 위상정렬 알고리즘

위상정렬 알고리즘은  BFS, DFS로 구현할 수 있다. 여기서는 BFS 원리를 이용한 위상정렬 알고리즘을 정리한다. 

# que 이용
1. 진입차수가 0인 모든 노드를 que에 넣는다. 
2. que가 빌 때까지의 아래 과정을 반복한다. 
  1) que에서 가장 왼쪽의 노드를 꺼내고, 해당 노드에서 나가는 간선을 제거한다. 
  2) 과정 1)에서 새롭게 전입차수가 0이 된 노드를 que에 넣는다.

위의 DAG를 사용하여 단계별로 알고리즘을 진행해보자.

 

[Step1]

노드별 진입차수를 정리한 후, 진입차수가 0인 노드를 que에 삽입한다. 

노드	0	1	2	3	4	5
진입차수	1	2	2	0	1	1

que

3

 

[Step2]

que에서 3을 꺼낸 뒤 노드 3에서 나가는 간선을 제거한다. 

 

새롭게 진입차수가 0이 된 노드들(0, 4)을 que에 삽입한다. 

노드	0	1	2	3	4	5
진입차수	0	2	2	0	0	1

 

que

0     4

 

[Step3]

que에서 0을 꺼낸 뒤 노드 0에서 나가는 간선을 제거한다. 

 

노드	0	1	2	3	4	5
진입차수	0	1	2	0	0	1

 

새롭게 진입차수가 0이 된 노드가 존재하지 않는다. 

que

4

 

 

[Step4]

que에서 4를 꺼낸 뒤 노드 4에서 나가는 간선을 제거한다. 

노드	0	1	2	3	4	5
진입차수	0	0	1	0	0	1

 

새롭게 진입차수가 0이 된 노드(1) 을 추가한다. 

que

1

 

 

[Step5]

que에서 1을 꺼낸 뒤 노드 1에서 나가는 간선을 제거한다. 

 

노드	0	1	2	3	4	5
진입차수	0	0	0	0	0	1

 

새롭게 진입차수가 0이 된 노드(2) 을 추가한다. 

que

2

 

 

[Step6]

que에서 2를 꺼낸 뒤 노드 2에서 나가는 간선을 제거한다. 

노드	0	1	2	3	4	5
진입차수	0	0	0	0	0	0

 

새롭게 진입차수가 0이 된 노드(2) 을 추가한다. 

que

5

 

 

que에 삽입된 전체 노드의 순서는 아래와 같다. 

 

3  → 0 → 4 → 1 → 2 → 5

 

이 결과는 위에서 보았던 위상정렬 예시1과 같다. 

 

 

♣ 백준 알고리즘 문제 이해(14567번)

 

 

 

 

 

이 문제는 전형적인 위상정렬 알고리즘으로 해결할 수 있다. 입력을 보면 첫째 줄에 과목의 수(N)와 선수 조건의 수(M)가 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 A, B 형태로 주어지는데, A번 과목이 B 과목의 선수 과목이다. 주어진 A, B의 크기는 항상 A < B 이다. 선수 관계를 지켜서 모든 과목을 이수할 때, 각 과목을 이수하는 데 걸리는 최소 학기를 구한다. 

 

 

♣ 알고리즘 코드

모든 과목을 이수하는 데 걸리는 학기 수를 구하기 위해서 과목의 선수 관계를 파악해야 한다. 

 

Step1. 노드의 관계와 진입차수 정보 넣기

 

nodes는 각 수업을 node로 나타내어서 각 수업이 가지는 선수 관계를 표시한다. indegrees는 각 수업(노드)가 가지고 있는 전입차수의 수를 표시한다. 

 

for 문을 보면 BFS 방식으로 부모 노드에 해당하는 index(a)에 자식 노드(b)를 넣는다. 여기서 부모 노드(a)가 자식 노드(b)에 진입차수가 되므로 자식 노드(b)의 진입차수에 1을 더한다. 위의 첫 번째 입력 예시를 이용하면 nodes와 indegrees가 아래와 같이 출력된다.

 

수업 선수 관계 이미지

 

1번에서 2번으로 전입하므로 nodes[1]에 2가 들어있고, 2번에서 3번으로 전입하므로 nodes[2]에 3이 들어있다. 또한 2, 3 노드가 각각 전입차수를 1개씩 가지고 있어서 indegrees는 [0, 0, 1, 1] 이 된다. 

 

 

Step2. 진입차수가 0인 노드를 que에 넣는다. 

 

각 노드가 가지는 진입차수를 순차적으로 없애야 한다. 처음에 진입차수가 0인 노드를 que에 집어넣는다.

 

 

Step3. 노드 탐색하며 진입차수 없애기

 

 

que에서 진입차수가 0인 노드를 순차적으로 꺼내서 해당 노드의 자식 노드(즉 선수 관계를 갖는 노드)를 탐색한다. parent가 자식 노드에 전입하므로 전입차수를 빼준다. (indegrees[x] -=1 ) 자식 노드를 이수해야 하는 학기는 total[x]와 total[parent]+1 중 제일 큰 것으로 설정한다. 왜냐하면 x에 진입차수가 여러 개일 수 있는데, 모든 선수관계를 다 지켜야 하기 때문에 모든 선수관계를 모두 고려한 최댓값이 답이 되어야 한다. 

 

그런 뒤 자식 노드의 진입차수가 0이면 que에 추가한다. 이런 식으로 que가 완전히 빌 때까지 작동한다. 

 

total [0, 1, 0, 0]

노드	1	2	3
진입차수	0	1	1

que

1

 

 

노드	1	2	3
진입차수	0	0	0

que

2     3

 

total 

[0, 1, 2, 0]
[0, 1, 2, 3]

 

노드	1	2	3
진입차수	0	0	0

que

3

 

노드	1	2	3
진입차수	0	0	0

que

 

최종적으로 index 0을 제외한 total 값이 각 과목을 이수하는 데 필요한 학기가 된다. 

 

♣ 참고 자료

https://yoongrammer.tistory.com/86

위상 정렬(Topological sort) 개념 및 구현

https://freedeveloper.tistory.com/390

[이것이 코딩 테스트다 with Python] 36강 위상 정렬