위상정렬

이 글을 많이 참고하여 작성하였습니다
https://m.blog.naver.com/ndb796/221236874984

위상정렬이란?

순서가 정해져있는 작업을 차례로 수행해야 할 때 순서를 결정해야 하는 알고리즘이다. 위상정렬은 DAG(Directed Acyclic Graph)에서만 사용할 수 있다. DAG는 사이클이 발생하지 않는 방향 그래프를 의미한다. 위상정렬 알고리즘 현재 그래프가 위상정렬이 가능한지 여부와 위상정렬이 가능하다면 그 결과는 어떤 가에 라는 2가지 결과물을 제공합니다. 위상정렬 알고리즘에는 큐를 사용하는 방식과 스택을 사용하는 방식 2가지가 존재한다. 여기서는 큐를 이용한 위상정렬 알고리즘을 소개하도록 한다.

위상정렬

큐를 활용하는 방법은 아래와 같다.

1. 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.
3. 간선을 제거한 후에 진입차수가 0이 된 정점을 큐에 삽입한다.
4. 큐가 빌 때까지 2번~3번 과정을 반복한다. 모든 원소를 방문하지 않았는데 큐가 종료된다면 싸이클이 존재한다는 뜻이다.

BaekJoon 2252

대표적인 위상정렬 문제이다. 학생들간의 크기 비교 자체를 그래프의 간선이라고 생각하고 학생들이 노드라고 생각한다면 학생들간의 순서를 결정하는 것이 위상정렬이라고 할 수 있다.

import sys
from collections import deque

N , M = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
inputVal = [0 for _ in range(N+1)]
result = []

for i in range(M):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    inputVal[end] += 1

q = deque()

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

while len(q) != 0:
    now = q.popleft()
    result.append(now)
    for i in graph[now]:
        inputVal[i] -= 1
        if inputVal[i] == 0:
            q.append(i)

print(*result)

여기서는 위상정렬이 가능한 그래프라는 것이 보장되어 있기 때문에 굳이 간선을 끊는 과정을 진행하지 않았다. 만약 싸이클이 발생하는 그래프라면 무한 루프에 빠질 것이라고 예상된다.