[백준 파이썬] 2252 줄 세우기

백준 2252번

뒤에 줄을 서는 학생은 선행되는 비교가 모두 끝난 후에 줄에 설 수 있고 키 순서대로이므로 사이클이 생기지 않는다. 위상 정렬 알고리즘은 이런 그래프에서 순서를 찾는 알고리즘이다.

위상 정렬로 풀기 위해서는 인접 리스트와 함께 진입 차수 배열이 필요하다. 진입 차수 배열은 해당 노드를 가르키는 간선이 몇 개인지 나타내는 배열이다.

예제 1번처럼 입력이 들어온다면 아래와 같다.

이 문제에서 진입 차수 배열은 idx번 째 학생보다 앞에 서게 될 학생은 몇 명이 있나로 볼 수 있다.
배열의 값이 0인 경우는 비교할 대상이 없어 가장 먼저 줄에 세워도 상관없다(문제 조건). 따라서 큐에 비교를 할 때마다 비교 대상의 진입 차수 값을 1씩 빼주고 0이 된다면 큐에 추가해주면(줄을 세우면) 된다.

from collections import deque

N, M = map(int, input().split())
compare = [list(map(int, input().split())) for _ in range(M)]

length = [[] for _ in range(N+1)] # 인접 리스트 초기화
in_degree = [0 for _ in range(N+1)] # 진입 차수 배열 초기화
lines = [] # 줄

for front, back in compare:
    length[front].append(back)
    in_degree[back] += 1 # 선행되는 비교 수 카운트

# 선행 비교 횟수가 0인 학생은 모두 큐에 추가
q = deque([i for i, val in enumerate(in_degree[1:], 1) if val == 0])

while q:
    front = q.popleft()
    lines.append(front) # 줄 세우기
    for back in length[front]:
        in_degree[back] -= 1 # 비교 횟수 차감
        if in_degree[back] == 0 # 남은 선행 비교 횟수가 0이라면 
            q.append(back) # 큐에 추가

print(*lines)

참고: 위상 정렬 이론 강의