[그래프] Python - 2252번, 줄 세우기

www.acmicpc.net/problem/2252

2252번: 줄 세우기

import sys

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
degree = [0 for _ in range(N+1)]

for _ in range(M):
    inputL, inputR = map(int, input().split())
    degree[inputR] += 1
    graph[inputL].append(inputR)

todo = []
for i in range(1, N+1):
    if degree[i] == 0:
        todo.append(i)

while todo:
    curHead = todo.pop(0)

    for node in graph[curHead]:
        degree[node] -= 1
        if degree[node] == 0:
            todo.append(node)
    print(curHead, end=" ")

 

degree라는 것을 부여하여, 출력 우선순위를 정한다.

degree가 0인 것들만을 담게 될 todo 리스트를 만들고, 이를 기준으로 출력해준다. 맨 앞의 것을 pop해주고, 그것보다 키가 작은 학생들을 돌면서 degree를 -1 해주는데, 해당 학생의 degree가 0이 될 경우 todo 리스트에 넣어준다.

 

이렇게 graph와 degree를 두 개를 이용하여 푸는 것이 핵심이다. graph는 입력받은 상하관계만을 저장해주되, degree에서 세부적으로 우선순위를 정하는 것이다.