#78 백준 파이썬 [2252] 줄 세우기 - 위상정렬

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

 

#Solution

해당 문제는 '사이클'이 없고 '방향'만 존재하는 그래프(DAG: Directed Acyclic Graph)에서 정점(Vertex)을 나열하는 방법으로 풀 수 있다. 이를 위상정렬 (Topological Sort)이라고 한다.

0) 정점과 연결된 다른 정점 리스트, 정점에 들어오는 그래프 개수 리스트 2개를 만들어준다.

 

1) 진입 루트(Indegree)가 없는 정점을 먼저 큐에 넣고

2) 해당 정점과 연결되어있는 노드에서 진입 루트 개수를 하나씩 빼준다.

3) 큐 앞에서부터 출력하고 제거한다. 다시 1)로 돌아가고 큐가 빌 때까지 반복한다.

DAG 그래프

num_student, num_compare = map(int, input().split())
graph_list = []
student_list = [[] for i in range(num_student + 1)]
indegree = [0 for i in range(num_student + 1)]
queue = []
result = []

#Graph Information

for i in range(num_compare):
    graph = list(map(int, input().split()))
    graph_list.append(graph)

#Node & Indegree Information

for [i, j] in graph_list:
    student_list[i].append(j)
    indegree[j] += 1
  
#Make First Queue

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

#Make Topological Sort Loop

while queue:
    for i in queue:
        temp = i
        queue.remove(i)
        result.append(temp)
        for j in student_list[temp]:
            indegree[j] -= 1
            if indegree[j] == 0:
                queue.append(j)
        
for i in result:
    print(i, end=' ')