[알고리즘] 29일차 (줄 세우기) #백준2252번

08-3 위상 정렬

• 위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
• 기능: 노드 간의 순서를 결정
• 특징: 사이클이 없어야 함
• 시간 복잡도(노드 수: V, 에지 수: E): O(V + E)
• 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다.
• 또한, 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

[위상 정렬의 핵심 이론]
1. 진입 차수는 자기 자신을 가리키는 에지의 개수이다. 인접 리스트에 기반을 두어 진입 차수 리스트에 D[N]++ 한다.
2. 진입 차수 리스트에서 진입 차수가 0인 노드를 선택하고, 선택된 노드를 정렬 리스트에 저장한다. 그 후, 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다. 이 과정을 모든 노드가 정렬될 때까지 반복한다.

📌 문제 053) 줄 세우기

시간 제한 2초, 골드 III, 백준 2252번

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.

4 2 # 노드 개수, 에지 개수
4 2
3 1

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

3 4 1 2

1단계 문제 분석

• 학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때, 노드 순서를 도출하는 가장 기본적인 문제이다. 특히, 답이 여러 개일 때 아무 것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수 있다.

1. 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열 값을 업데이트한다.
2. 다음 순서에 따라 위상 정렬을 수행한다.
   (1) 진입 차수가 0인 노드를 큐에 저장한다.
   (2) 큐에서 데이터를 뽑아와서 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.
   (3) 감소했을 때 진입 차수가 0이 되는 노드를 큐에 삽입한다.
   (4) 큐가 빌 때까지 (1)~(3)을 반복한다.

2단계 슈도 코드

N(학생 수) M(비교 횟수)
A(비교 데이터 저장 인접 리스트)
indegree(진입 차수 리스트)

for M만큼 반복:
	인접 리스트 데이터 저장
    진입 차수 리스트 초기 데이터 저장

# 위상 정렬 수행
큐 생성

for N만큼 반복:
	진입 차수 리스트의 값이 0인 학생(노드)을 큐에 삽입

while 큐가 빌 때까지:
	현재 노드 = 큐에서 데이터 가져오기
    현재 노드값 출력
    for 현재 노드에서 갈 수 있는 노드의 개수:
    	타깃 노드 진입 차수 리스트값 1 감소
        if 타깃 노드의 진입 차수가 0이면:
        	큐에 타깃 노드 추가

3단계 코드 구현

from collections import deque
N, M = map(int, input().split())
A = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1) # 진입 차수 리스트

for i in range(M):
    S, E = map(int, input().split())
    A[S].append(E)
    indegree[E] += 1 # 진입 차수 데이터 저장

queue = deque()

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

while queue: # 위상 정렬 수행
    now = queue.popleft()
    print(now, end=' ')
    for next in A[now]:
        indegree[next] -= 1
        if indegree[next] == 0:
            queue.append(next)