[알고리즘] 위상 정렬

위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 해결할 때 사용됩니다.

위상 정렬의 전제와 조건

1. 방향 그래프: 위상 정렬은 방향성을 가진 간선으로 이루어진 그래프에서만 수행됩니다.
2. 사이클이 없어야 함: 위상 정렬을 수행할 그래프는 순환이 없어야 합니다. 순환이 있는 경우, 어떤 노드를 먼저 방문해야 하는지 정할 수 없기 때문입니다.

위상 정렬 설명

1. 진입 차수 계산: 각 노드의 진입 차수(들어오는 간선의 수)를 계산합니다.
2. 진입 차수가 0인 노드 찾기: 진입 차수가 0인 노드를 찾고 큐에 넣습니다. 이 노드들은 의존성이 없는 작업이므로 먼저 수행될 수 있습니다.
3. 노드 제거와 진입 차수 갱신: 큐에서 노드를 하나씩 제거하고 해당 노드에서 나가는 간선을 제거합니다. 이로 인해 연결된 노드의 진입 차수가 감소하며, 이 과정에서 진입 차수가 0이 된 노드를 큐에 추가합니다.
4. 순서 생성: 3 단계에서 큐에서 제거되는 노드의 순서가 바로 위상 정렬의 순서가 됩니다.
5. 반복 실행: 큐가 빌 때까지 3-4 단계를 반복합니다.
6. 결과 반환: 모든 노드를 방문한 순서를 반환합니다.

위상 정렬은 일반적으로 작업 스케줄링, 컴파일러의 명령어 스케줄링, 프로젝트 관리 등과 같은 다양한 분야에서 활용됩니다. 일반적인 시간 복잡도는 O(V + E)로, 여기서 V는 노드의 수, E는 간선의 수입니다.

위상 정렬은 그래프가 순환을 포함하지 않는 한 항상 가능하며, 그래프에 순환이 있다면 위상 정렬은 불가능합니다.

 

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

코드 예시

# 2252번 줄 세우기

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]
numOfEdges = [0 for _ in range(n+1)]
queue = deque()
answer = []

for i in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    numOfEdges[b] += 1

# 위상정렬 큐에 집어넣기 위해서 진입 간선이 0개인 노드를 고른다.
for i in range(1, n+1):
    if numOfEdges[i] == 0:
        queue.append(i)

while queue:
    c_n = queue.popleft()
    answer.append(c_n)
    # 진출 차선에 연결된 노드 추출.
    for i in graph[c_n]:
        numOfEdges[i] -= 1
        if numOfEdges[i] == 0:
            queue.append(i)

print(*answer)