문제 링크: https://www.acmicpc.net/problem/2252

위상 정렬을 구현하는 정석적인 문제입니다.

풀이

위상 정렬?

위상 정렬이란, 순서가 정해져 있는 작업을 차례대로 수행하기 위해 그 순서를 결정해주는 알고리즘입니다. 방향 그래프에서, 모든 정점을 순서대로 방문하는 일직선의 순서를 찾는 방법이라고 생각하면 됩니다.

위상 정렬은 일반적으로 DAG (Directed Acyclic Graph)에만 적용 가능합니다. 다시 말해, 방향 그래프이면서 사이클이 없는 그래프에만 사용할 수 있습니다.
사이클이 있는 경우, 위상 정렬의 시작점을 명확히 정할 수 없기 때문입니다.

또, 한 개의 그래프에서 위상 정렬의 결과는 여러 개일 수 있습니다.

위상 정렬 구현

위상 정렬은 스택 또는 큐를 사용해 구현할 수 있습니다. 저는 큐를 사용해 구현했습니다.

과정은 다음과 같습니다:

1. 모든 간선 입력을 기록하면서, 각 정점의 진입 차수(In-Degree)를 기록합니다.
   * 진입 차수: 해당 정점으로 들어오는 간선의 개수
2. 이후, 큐에 진입 차수가 0인 모든 정점을 추가합니다.
3. 정점의 개수만큼 다음을 반복합니다:
   1. 큐에서 원소를 하나 꺼내옵니다. 이를 cur이라고 부르겠습니다.
      1. 만약 큐가 비어있어 원소를 꺼낼 수 없다면, 사이클이 발생한 경우입니다.
         탐색을 종료합니다. (위상 정렬 불가)
      2. 꺼낸 원소는 위상 정렬의 결과로 적절히 기록해 줍니다.
   2. 해당 정점에서 다른 정점으로 가는 모든 간선을 제거합니다.
      각 간선의 도착점(cur이 아닌 다른 정점)을 next라고 할 때, next의 진입 차수를 1 감소시킵니다.
   3. 이때, 진입 차수가 0이 된 정점이 있다면 큐에 추가합니다.

전체 코드

from collections import deque
input = open(0).readline

N, M = map(int, input().split())
in_degree = [0 for _ in range(N + 1)] # 각 정점의 진입 차수를 기록하는 배열
edges = [[] for _ in range(N + 1)] # 그래프의 간선 정보 기록
result = [0 for _ in range(N)] # 위상 정렬된 결과를 기록할 배열

for _ in range(M):
    u, v = map(int, input().split())
    edges[u].append(v)
    in_degree[v] += 1

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

for i in range(N):
    if len(queue) == 0:
        break

    cur = queue.popleft()
    result[i] = cur

    for next in edges[cur]:
        in_degree[next] -= 1
        if in_degree[next] == 0:
            queue.append(next)

print(*result)