위상정렬 알고리즘 (boj_2252)

용도

• 순서가 정해져 있는 일련의 작업을 차례대로 수행할 때 사용하는 알고리즘이다.
• 사이클이 없을 때 사용이 가능하다. (있다면 아마 변형이 필요할 것)
• 예시는 수강신청이 있다. 기초수학-대학수학- 공업수학, 기초수학-물리학, 물리학-양자역학 등의 커리큘럼이 있을 때, 위 선수과목을 어긋나지 않고 순서대로 듣는 알고리즘을 짜는 법이다.

        ⇒ 이 글에서는 수강신청을 예시로 많이 들 예정이다.

용어 설명

• 진입 차수 - 선수과목 수(나에게 들어오는 노드 간선의 수)
• 진출 차수 - 후수과목 수(내가 다른 노드로 뻗는 간선의 수)

위상 정렬 알고리즘 로직

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.

• 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

        ⇒ 제거한 그래프를 출력 또는 다른 리스트에 삽입해서 기록하면 그것이 과목을 들어야하는 순서가 된다!

• 새롭게 진입차수가 0이 된 노드를 큐에 삽입

로직 상세 설명

위 그림을 예시로 사용한다.

1. 진입차수가 0인 노드를 큐에 넣는다. (선수과목이 없는 과목을 수강신청한다)

2. 큐에서 1번을 제거하고 1번이 가리키는 2, 5의 진입차수를 -1한다

        ⇒ 이 때, 진입차수가 0이 된다면 선행조건이 없는 것이 된다

        ⇒ 따라서, 진입차수가 새롭게 0이 된 노드들을 큐에 넣는다.

        ⇒ 만약, 큐가 비었는데 진입차수가 모두 0이 아니라면 해당 업무들은 현재 수행하는 충분한 조건이 없는 상태이다.

        ⇒ 싸이클이 있을 경우, 이런 경우가 발생하여 싸이클이 없는 DAG에서만 수행가능하다

**※ DAG (Direct Acyclic Graph)** : 순환하지 않는(=사이클이 없는) 방향 그래프

3.큐에서 먼저 들어온 요소를 pop하여 다시 반복한다.

        ⇒ 이 과정을 반복하면 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7 이 나오게 된다.

        ⇒ 상세과정은 참고문서를 보길 바란다.

이 과정은 모든 노드와 간선을 확인하는 시간은 O(V) + O(E) = O(V+E)가 나온다.

파이썬 코드

from collections import deque
n, m = map(int,input().split())
nodes = [[] for i in range(n + 1)]
indegree = [0 for _ in range(n+1)]

for i in range(m):
    a, b = map(int,input().split())
    nodes[a].append(b)
    indegree[b] += 1

def topology_sort():
    result = []
    q = deque()

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

    while q:
        now = q.popleft()
        result.append(now)
        for i in nodes[now]:
            indegree[i] -=1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=' ')

topology_sort()

 

참고문서

• velog : https://velog.io/@kimdukbae/위상-정렬-Topological-Sorting