📌 문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

📌 입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

📌 출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

📌 문제 풀이

👨‍🏫 접근

모든 정점을 주어진 순서에 따라 순회해야 한다. 이럴 때 사용하는 알고리즘이 위상정렬이다.

우리가 졸업을 하기 위해서는 주어진 커리큘럼을 순서를 따라서 잘 지켜야 졸업할 수 있다. 해당 전공 수업을 듣기 위해서 선행 수업을 모두 들어야 그 수업을 들을 수 있다. 이처럼, 정점과 정점은 일정 관계가 존재한다. 이처럼 위상정렬은 일정한 관계를 지키는 조건에서 정점을 정렬한다.

예를 들어, A -> B, B -> C, X ->C 라는 경로가 있다고 한다면, 주어진 규칙에 따라서 모든 경로는 A, B, X, C나 A, X, B, C 혹은 X, A, B, C의 순서로 정렬할 수 있다. 이처럼, 위상정렬은 답이 여러 개 나올 수 있다.

위상 정렬을 수행하기 위해서는 스택과 큐를 사용하는데 보통 큐를 많이 사용한다. 그리고 정점에서 다른 정점으로 이동하는 방향의 개수를 테이블에 초기화한다. 이 방향이 모두 처리 되어야만 해당 정점으로 이동할 조건이 충족되기 때문에 사용한다. 앞선 예제에서는 C의 indegree(C로 들어오는 방향)가 2, B는 1, A와 X는 0이다. 이 의미는 A와 X는 이전에 수행되어야 하는 순서가 없기 때문에 순서에 국한되지 않고 자유롭게 정렬될 수 있다는 의미이다. 반면, B는 A를 방문한 후에 방문해야 하며, C는 B와 X를 방문한 후에 방문해야 한다.

정리하면 다음과 같다.

indegree가 없는 모든 정점을 방문한다(순서는 상관이 없기 때문에 모든 정렬을 마치고 가장 나중에 방문할 수도 있다).
정점을 방문하면서 indegree가 모두 사라진 정점도 방문할 수 있기 때문에 방문한다.

이때, 중요한 것은 사이클이 발생하면 안된다. 사이클이 발생하면 순서를 가질 수 없기 때문이다.

이러한 사실을 토대로 아래와 같이 알고리즘의 흐름을 작성할 수 있다.

from collections import deque

v, e = map(int, input().split())
graph = [[] for _ in range(v + 1)]
indegree = [0] * (v + 1)

for _ in range(e):
	a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
    
def topology_sort():
	result = []
    q = deque()
    
    for i in range(1, v + 1):
    	if indegree[i] == 0:
        	q.append(i)
            
    while q:
    	now = q.popleft()
        result.append(now)
        for i in graph[now]:
        	indegree[i] -= 1
            if indegree[i] == 0:
            	q.append(i)
                
	for i in result:
    	print(i, end=' ')
        
topology_sort()

👨‍🏫 문제 풀이

📄 전체 코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().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:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

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


topology_sort()

📄 준비

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().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:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

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


topology_sort()

📌 총평

알고리즘은 모든 코드를 외우고 있는 것보다는 어떻게 동작하는 지를 이해하고 이를 토대로 스스로 작성해보는 것이 좋다. 왜냐하면 단독으로 쓰이는 경우도 많지만, 변형하여 사용하는 경우가 상당히 많기 때문이다.

저작자표시 비영리 (새창열림)