[알고리즘] 위상 정렬(Topological Sort) - 줄 세우기, 선수 과목

위상 정렬(Topological Sort)

• 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬
• ex. 선수 과목 : 특정 과목에 선수 과목이 있을 경우 선수 과목부터 수강해야 하는 상황에서 위상정렬으로 순서 찾기 
• 그래프 순환이 존재하지 않아야 한다.
• DAG(Directed Acyclic Graph) : 사이클이 존재하지 않는 방향 그래프

 

위상 정렬의 수행 과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾는다.

2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제한다.

3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료한다.

 

 

위상 정렬 알고리즘

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채운다.

2. indegree가 0인 정점들을 모두 큐에 넣는다.

3. 큐에서 정점을 꺼내 위상 정렬 결과에 추가한다.

4. 해당 정점으로부터 연결된 모든 정점의 indegree 값ㅇ르 1 감소시키고, indegree가 0이 되면 정점을 큐에 추가한다.

5. 큐가 빌 때까지 3,4번을 반복

 

 

위상 정렬 문제 - 2252번 줄 세우기 

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

from collections import deque
#n, m = 3, 2 # 학생의 번호 1~n, m는 키를 비교환 횟수
n, m = map(int, input().split())
inDegree = [0]*(n+1)
graph = [[] for i in range(n+1)]
queue = deque()
answer = []
arr = []
# 1 -> 3
# 2 -> 3

# 키를 비교한 두 학생의 번호 a,b (학생 a가 b앞에)
# 그래프에 정점끼리 연결된 정보들 입력
for _ in range(m):
    a, b = map(int, input().split())
    arr.append([a,b])

for a, b in arr:
    inDegree[b] += 1
    graph[a].append(b)

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

while queue:
    top = queue.popleft() # 큐 최상위 정점
    for b in graph[top]:
        inDegree[b] -= 1
        if inDegree[b] == 0:
            queue.append(b)
    answer.append(top)

print(*answer)