[줄 세우기] 위상 정렬 | python 2252번

위상 정렬 (Topological sort)

위상 정렬은 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것이다.
방향 그래프에서 간선 <u,v>가 있다면, 정점 u는 정점 v를 선행하여 정렬한다.
방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열해야한다.

활용 예로는 선수 과목은 과목들의 선행 관계를 표현한다.

구현

정점에 들어오는 간선수를 저장하는 진입차수(in_degree)를 사용한다.

동작방식

1. 모든 정점의 in_degree 설정
2. 순서에 맞도록 리스트 설정 예) graph[2] = [1,3] : 정점 2는 정점 1과 정점 3보다 선행함.
3. in_degree가 0인 정점은 큐에 추가
4. 큐가 빌 때까지 반복
   3.1 큐의 앞 요소를 popleft()로 가져와 그에 맞는 리스트를 꺼냄
   3.2 리스트에서 나온 정점의 in_degree를 1 감소함
   3.3 in_degree가 0인 정점은 큐에 추가한다.

---

문제

줄 세우기

풀이

추가입력

6 7
4 1
4 5
1 2
5 2
5 3
2 3
3 6

1. in_degree 설정

[1]	[2]	[3]	[4]	[5]	[6]
1	2	2	0	1	1

2. graph 설정

[1]	[2]	[3]	[4]	[5]	[6]
[2]	[3]	[6]	[1,5]	[2,3]	[ ]

3. in_degree가 0인 정점은 큐에 추가
queue = [4]

4. quqeue가 빌 때까지
step 1.
queue.popleft()로 4가 나온 후, result에 4 추가.
graph[4]에 해당하는 정점1과 정점5의 indegree를 1 감소한다.

indegree가 0인 정점1과 정점5를 queue에 넣는다.

queue = [1,5]
indegree

[1]	[2]	[3]	[4]	[5]	[6]
0	2	2	0	0	1

step 2.
queue.popleft()로 1이 나온 후, result에 1 추가.
graph[1]에 해당하는 정점2의 indegree를 1 감소한다.

queue = [5]
indegree

[1]	[2]	[3]	[4]	[5]	[6]
0	1	2	0	0	1

step 3.
queue.popleft()로 5가 나온 후, result에 5 추가.
graph[5]에 해당하는 정점2와 정점3의 indegree를 1 감소한다.

indegree가 0인 정점2를 queue에 넣는다.

queue = [2]
indegree

[1]	[2]	[3]	[4]	[5]	[6]
0	0	1	0	0	1

step 4.
queue.popleft()로 2가 나온 후, result에 2 추가.
graph[2]에 해당하는 정점3의 indegree를 1 감소한다.

indegree가 0인 정점3를 queue에 넣는다.

queue = [3]
indegree

[1]	[2]	[3]	[4]	[5]	[6]
0	0	0	0	0	1

step 5.
queue.popleft()로 3가 나온 후, result에 3 추가.
graph[3]에 해당하는 정점6의 indegree를 1 감소한다.

indegree가 0인 정점6를 queue에 넣는다.

queue = [6]
indegree

[1]	[2]	[3]	[4]	[5]	[6]
0	0	0	0	0	0

step 6.
queue.popleft()로 6가 나온 후, result에 6 추가.
queue가 빈다.

5. result 출력

4 1 5 2 3 6

코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())

in_degree = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
queue = deque()

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    in_degree[b] += 1

# print(in_degree)
# print(graph)

# 진입 차수가 0이면 추가
for i in range(1, N + 1):
    if in_degree[i] == 0:
        queue.append(i)

answer = []
while queue:
    now = queue.popleft()
    answer.append(now)

    # print("in_degree:", in_degree)

    for next in graph[now]:
        in_degree[next] -= 1
        if in_degree[next] == 0:
            queue.append(next)

for a in answer:
    print(a, end=' ')