위상 정렬(Topological Sort)

위상 정렬이 뭔지 알아보기전에 빠른 이해를 위해 실생활에서 예를 들어보자.

 

위상 정렬의 예시를 들때, 항상 빠지지 않고 등장하는 대학교의 선수 과목 제도를 생각해보자.

 

프로그래밍 → 프로그래밍2 → 객체지향 프로그래밍

프로그래밍 → 자료구조 → 알고리즘

이산수학 → 알고리즘

 

위와 같이 특정 과목에 따른 선수과목들이 있다고 하자.

 

수강을 하는 순서로는 다양한 방법들이 존재한다.

 

이산수학, 프로그래밍1, 프로그래밍2, 자료구조, 알고리즘, 객체지향 프로그래밍 순으로 들어도 되고, 이산수학을 안 듣고 프로그래밍1, 프로그래밍2, 객체지향 프로그래밍, 자료구조를 듣다가 알고리즘 과목을 듣기전에 이산수학을 들어주면 된다.

 

그러나 선수 과목을 지켜야하기 때문에, 이산수학을 안듣고 알고리즘을 들을 순 없다.

실제 c++ 언어로 진행했던 프로그래밍2 과정을 안 듣고 객체지향 프로그래밍을 들었는데, 따라가는데 엄청 힘들었던 경험이 있다… 주륵..

---

 

위상 정렬은 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬 방법이다.

위 그래프를 보면, 5에서 11로가는 간선이 있으니 정렬을 했을 때, 5는 11보다 앞에 등장해야한다. 그러나 11은 자신으로 들어오는 간선들이 많이 있으니 5보도 앞설 순 없다.

 

그리고 실생활 예시를 통해서 보았드시 여러가지의 위상정렬 결과가 있을 수 있다.

• 5, 7, 3, 11, 8, 2, 9, 10
• 3, 5, 7, 8, 11, 2, 9, 10
• 5, 7, 3, 8, 11, 10, 9, 2
• 7, 5, 11, 3, 10, 8, 9, 2
• 7, 5, 11, 2, 3, 8, 9, 10
• 3, 7, 8, 5, 11, 10, 2, 9

만약 그래프 내에 사이클이 존재할 경우에는 올바른 위상 정렬이 존재할 수 없다. 그래프에 사이클이 존재한다면 간선으로 주어진 정점 간 선후관계에 모순이 발생하기 때문이다.

 

그래서 위상 정렬은 사이클이 존재하지 않는 방향 그래프에서만 잘 정의된다. 사이클이 존재하지 않는 방향 그래프를 DAG(Directed Acyclic Graph)라고 줄여서 부르기도 한다.

 

위상 정렬을 사용할 때 쓰이는 용어들을 한 번 정리해보자.

자기 자신으로 들어오는 간선을 진입 차수(indegree)라고 한다. 위 그래프의 11의 경우 진입차수는 2이다. (5와 7로부터 들어온다.)

그리고 자기 자신으로부터 나가는 간선을 진출 차수(outdegree)라고 한다. 11의 경우는 진출 차수가 3개이다.

정점 5의 경우 진입 차수는 0, 진출 차수는 1이다.

정렬 과정

위상 정렬은 다음과 같이 진행된다.

1. 들어오는 간선이 없는 정점을 모두 큐에 넣는다
2. 그다음 큐에 있는 정점을 하나 빼고 그 정점에서 나가는 간선을 모두 삭제한다. 이 때 나가는 간선이 삭제됨으로써 새로이 진입차수가 0인 정점들이 생기는데, 이 또한 큐에 넣어준다.
3. 큐에서 빼는 순서가 위상 정렬의 결과이다.

위에서 사이클이 생기면 위상 정렬을 할 수 없다고 했는데, 사이클이 있는 그래프가 위상정렬을 실행하면 큐가 비어 버리므로 정렬이 불가능해 진다.

---

이제 위상 정렬을 코드로 어떻게 구현해야 할 지 문제를 보면서 고민해보자.

 

줄 세우기

2252번: 줄 세우기

2252번: 줄 세우기

줄 세우기 문제는 딱, 위상 정렬을 위한 문제이다.

입력으로 정점간의 간선 정보가 주어진다.

1 3
2 3

위의 입력을 보면, 1번 학생은 3번 학생보다 키가 작고, 2번 학생은 3번 학생보다 키가 작다.

 

눈때중으로만 봐도 1→2→3 또는 2→1→3 순으로 줄을 세우면 될 듯하다.

 

이를 인접 리스트로 받아보면 다음과 같다.

idx 1 : [3]
idx 2 : [3]
idx 3 : []

정점 3으로 들어오는 간선은 총 2개가 있는것을 볼 수 있다. 그래서 정점 3이 정렬을 진행했을 때 가장 뒤로 가야함을 알 수 있다.

 

해결방법

진입 차수를 세줄 배열을 하나 만든다. 그리고 진입차수가 0인 정점들을 큐에 전부 집어넣는다.

이후 큐에있는 정점들을 하나씩 빼면서 결과를 저장할 result 배열에 넣어준다.

그 다음 해당 정점에 연결된 정점에서 진입차수를 하나 빼준다.

만약 진입차수를 뺏을 때 그 정점의 진입차수가 0이 된다면 그 정점도 큐에 넣어준다.

 

이 과정을 정점의 갯수만큼 반복하고 나면 정렬이 완성된다.

 

코드

# 줄세우기
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[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:
        cur = q.popleft()
        result.append(cur)

        for i in graph[cur]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    for i in result:
        print(i, end = ' ')
topology_sort()

 

 

---

장난감 조립

2637번: 장난감 조립

2637번: 장난감 조립

장난감 조립 문제는 완성품을 만들기 위해서 몇개의 기본 부품, 중간 부품들이 필요한지 묻는 문제이다. 완전제품과 중간 부품은 기본부품을 사용해서 만들어지기에, 위상 정렬을 통해서 접근하면 풀 수 있다.

 

예를 들어 완전제품 7은 2개의 중간 부품 5, 3개의 중간 부품 6과 5개의 기본 부품 4로 만들어진다.

그리고 중간 부품 6은 2개의 중간 부품 5, 3개의 기본 부품 3과 4개의 기본 부품 4로 만들어진다. 또한

중간 부품 5는 2개의 기본 부품 1과 2개의 기본 부품 2로 만들어진다.

 

문제 해결 과정에서 각 부품을 만들기위해 필요한 부품들의 갯수를 저장하기 위해 2차원 배열을 만들어 저장했다.

기본 부품을 사용할 땐 다음과 같이 저장했다.

result[next][cur] += part_need

예를 들어 중간부품 5의 경우 기본 부품 1이 2개 필요하기 때문에 graph[5][1] = 2 와 같이 필요한 기본 부품을 저장했다.

 

그러나 중간부품이 사용될 땐 조금 달리 접근해야한다.

중간 부품 5의 간선 정보를 보면 아래처럼 저장해뒀는데, 5는 7을 만들 때 2개, 6을 만들 때 2개가 필요하다.

5 : [(7, 2), (6, 2)]

 

그래서 필요한 기본 부품수를 알기위해 graph[5][1]의 값에 필요한 부품수가 저장돼있는 part_need를 곱하여 더해준다.

그렇기 때문에 7을만들기 위해선 5가 2개, 5가 2개 만들어지기 위해서는 1이 2개 때문에 7을 만들기위해 필요한 1의 갯수는 5때문에 2 * 2 가 된다.

# cur에는 5, next에는 7(완전 제품)이 저장돼있다.
for i in range(1, n+1):
    result[next][i] += result[cur][i] * part_need

 

또한 7은 중간 부품 6도 필요하기 때문에 위 같은 방법으로 기본 부품 3, 4를 사용한다.

 

결과적으로 위와 같은 result 배열이 만들어진다.

코드

# 장난감 조립
import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
result = [[0 for _ in range(n+1)] for _ in range(n+1)]
res = [0] * (n+1)

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

def check_midle(part_list):
    cnt = 0
    for part in part_list:
        if part == 0:
            cnt += 1
    if cnt == n + 1: False
    else: return True

def t_sort():

    q = deque()

    for i in range(1, n+1):
        # 진입차수가 0인 정점을 큐에 넣는다.
        if indegree[i] == 0:
            q.append(i)
        
    while q:
        cur = q.popleft()
        
        for next, part_need in graph[cur]:
            # 5 -> (7,2)
            if not check_midle(result[cur]):
                result[next][cur] += part_need
            else:
                for i in range(1, n+1):
                    result[next][i] += result[cur][i] * part_need

            
            indegree[next] -= 1
            if indegree[next] == 0:
                q.append(next)
            
t_sort()
for i in range(1, n+1):
    if result[n][i] != 0:
        print(f"{i} {result[n][i]}")