파이썬(Python) 위상정렬 - 개념과 예제 (백준 2252)

위상 정렬

위상정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다.
사이클이 있다면 노드 순서가 정의되지 않고, 위상정렬은 항상 유일한 값으로 정렬되진 않습니다.

그래프가 있을때 인접리스트와 진입차수 리스트를 만들어야 합니다. 진입차수리스트는 자신을 가리치는 노드의 갯수를 의미하고, 인접리스트를 이용해서 만들수 있습니다.

adjacent (인접리스트)

1 -> 2 3
2 -> 4 5
3 -> 4
4 -> 5
5

진입 자수 리스트 (in-degree)

각 노드마다 자신을 가리키는 노드의 갯수를 기록 하면 됩니다. 예를 들어 4는 2,3이 가리키고 있으므로 2입니다.

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

진입 차수 리스트에서 차수가 0인 것을 우선 선택하고 위상 정렬 리스트 첫번째에 추가해줍니다.
노드 1의 차수가 0이므로 먼저 위상정렬 리스트에 추가하고 제외해줍니다.

위상정렬

1

그리고 1의 인접 노드들의 차수를 1씩 낮춥니다.
-> 노드 1을 제외했으므로 1의 인접노드들을 자신을 가리키는 노드1이 없어진 것입니다.
그러므로 차수를 1씩 낮춥니다.

노드		2	3	4	5
차수		0	0	2	2

---

다음에 차수가 0인 노드 둘중 하나를 선택합니다. (보통 구현할때 둘다 큐에 넣어서 차례대로 처리해줍니다.)
2를 선택하면 위상정렬 리스트에 추가하고, 2의 인접리스트에 해당하는 노드(4,5)들의 차수를 1씩 내립니다.

노드			3	4	5
차수			0	1	1

위상정렬

1

2

이와 같은 방식을 반복하면 아래와 같이 나올 것입니다.
예시에서는 차수가 0인 노드가 두개 이상 있을때 숫자가 적은 것 부터 탐색했는데, 어떤 것을 먼저 탐색하느냐에 따라서 다양한 위상 정렬이 나올수 있습니다.

위상정렬

1

2

3

4

5

---

줄 세우기

 

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

 

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

3 2
1 3
2 3

예제 출력 1

1 2 3

---

파이썬 코드

앞에서부터 줄을 세운 결과를 출력하는 것이고, A,B가 주어졌을때, 학생 A가 학생 B의 앞에 서야 한다는 의미를 보면 A -> B 순서로 탐색한다는 것을 알수 있습니다.
그러므로 A -> B 씩으로 인접리스트(adjacent)를 작성하고, 인접리스트 작성과 동시에 진입차수리스트(in_degree)를 구합니다.
초기화 할땐 0인것을 반복문으로 탐색하고 미리 큐에다가 넣어줄 것입니다.
그러나 탐색할때마다 차수가 0인것을 반복문으로 탐색해서 처리하는것은 시간이 너무 오래 걸립니다. 그러므로 0이 되는 것을 큐에다가 넣어서 처리할 것인데요, 차수는 한 노드의 인접리스트들을 탐색할때 1씩 감소합니다.
인접리스트를 탐색할때 그 인접노드의 차수가 1이면 곧 0이 되는 노드이므로 큐에다가 넣어서 처리합니다.

# 위상 정렬
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
adjacent = [[]for _ in range(n+1)]
in_degree = [0]*(n+1) # 진입 차수 리스트
in_degree[0] = -1
for i in range(m):
    a,b = map(int, input().split()) # a -> b
    adjacent[a].append(b)
    in_degree[b] += 1

queue = deque()
for i in range(1, n+1):
    if in_degree[i] == 0:
        queue.append(i)

while queue:
    node = queue.popleft()
    print(node,end=' ')
    for i in adjacent[node]:
        if in_degree[i] == 1:
            queue.append(i)
        in_degree[i] -= 1