백준 2252번: 줄 세우기 (Python)

접근

위상 정렬에 대한 공부를 하고 나서 풀었다. 위상 정렬은 사이클이 없고, 방향만 존재하는 그래프에서 정점들을 나열하는 방법이다.

학생들의 순서를 앞 학생에서 뒤 학생으로 연결된 한개의 방향 화살표라고 할 때, 뒤 학생에는 진입루트가 한개 증가한 것이다. 주어진 비교 측정들을 모두 확인하여 뒤에 있는 학생들의 진입루트를 한개씩 더해주고 나서 보았을 때, 진입루트가 없는 학생은 가장 앞에 서게 될 것이다.

따라서 진입 루트가 0인 학생들을 모두 queue에 넣고 해당 학생들과 연결된 학생들의 진입루트를 한개씩 없애준다. 이 과정에서 진입 루트가 0이 된 학생은 추가로 queue에 넣어주게 된다. 진입 루트가 0이 되었다는 말은 앞선 학생들이 빠지고 난 상황에서 가장 앞에 있다는 의미이기 때문이다.

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
q = deque()
graph_list = []
student_list = [[] for _ in range(n + 1)]
in_degree = [0 for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    in_degree[b] += 1
    student_list[a].append(b)

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

while q:
    now = q.popleft()
    print(now, end=" ")
    for d in student_list[now]:
        in_degree[d] -= 1
        if in_degree[d] == 0:
            q.append(d)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!