위상 정렬이란? - python 파이썬

오늘은 위상 정렬(Topological Sort)에 대해서 공부했다.

위상 정렬이란?

'순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 순서를 결정할 때 사용하는 알고리즘이다. 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으며 모든 정점을 나열하면 된다. 하나의 방향 그래프에는 여러 개의 위상 정렬이 가능하다.

 

그럼 그래프를 통해서 이해해보자

위와 같은 그래프가 주어졌다고 가정해보자. 이 그래프가 의미하는 것은 다음과 같다.

1번의 선행 노드: 없음

2번의 선행 노드: 없음

3번의 선행 노드: 1번

4번의 선행 노드: 1번

5번의 선행 노드: 2번

6번의 선행 노드: 3번, 4번, 5번

 

1,2번은 선행 노드가 없다. 이런 정점을 진입 차수가 0인 정점이라 부른다. 진입 차수가 0인 정점을 시작으로 경로를 만들어나갈 것이다.

 

풀이 방법

방법은 간단하다.

1. 진입 차수가 0인 정점을 Queue에 넣는다.

2. Queue에서 하나의 정점을 선택한다.

3. 선택한 정점을 Queue에서 삭제하고 위상 순서에 추가한다.

4. 선택한 정점에 연결된 모든 간선을 삭제한다.

5. 1~4번을 반복한다.

 

좀 더 자세하게 알아보자.

indegree: 들어오는 간선의 수

주어진 그래프의 indegree가 0인 노드는 1,2번이다.

 

먼저 1번을 선택해보자. (2번을 시작점으로 설정해도 무방하다)

1번과 3,4번이 연결된 간선을 삭제한 후, 1번을 Queue에서 삭제한다. indegree = [0,0,0,0,1,3]이 된다. 3,4번은 1번과 연결되어있던 간선이 삭제되었으므로 indegree가 0인 노드가 된다. 따라서 Queue에 3,4번을 추가해준다. queue = [2,3,4] Queue에서 삭제한 정점은 위상순서에 넣어준다. 위상순서 = [1]

 

그다음 2번을 선택하자.

2번과 5번이 연결된 간선을 삭제한 후, 2번을 Queue에서 삭제한다. indegree = [0,0,0,0,0,3]이 된다. 위와 마찬가지로 5번은 2번과 연결되어있던 간선이 삭제되었기에 indegree가 0인 노드가 된다. 따라서 Queue에 5번을 추가해준다. queue = [3,4,5] 위상순서 = [1,2]

그다음 3번을 선택하자.

3번과 6번이 연결된 간선을 삭제한 후, 3번을 Queue에서 삭제한다. indegree = [0,0,0,0,0,2]이 된다. 위와는 다르게 6번은 아직 2개의 연결된 간선이 있기 때문에 Queue에 추가할 수 없다. queue = [4,5] 위상 순서 = [1,2,3]

 

4번을 선택하자.

4번과 6번이 연결된 간선을 삭제한 후, 4번을 Queue에서 삭제한다. indegree = [0,0,0,0,0,1]이 된다. 마찬가지로 6번은 아직 1개의 연결된 간선이 있기 때문에 Queue에 추가할 수 없다. queue = [5] 위상 순서 = [1,2,3,4]

 

5번을 선택하자.

5번과 6번이 연결된 간선을 삭제한 후, 5번을 Queue에서 삭제한다. indegree = [0,0,0,0,0,0]이 된다. 마침내 6번을 queue에 추가할 수 있게 되었다. queue = [6] 위상 순서 = [1,2,3,4,5]

 

6번을 선택하자.

indegree = [0,0,0,0,0,0] queue = [] 위상순서 = [1,2,3,4,5,6]

 

알고리즘 - 파이썬

이를 알고리즘으로 나타내면 다음과 같다.

n = int(input()) # 그래프 정점의 수
graph = [[] for _ in range(n+1)]

for i in range(n):
    a, b = map(int, input().split())

    graph[a].append(b)	#a는 b의 선행 노드
    indegree[b] += 1	#b의 들어오는 간선의 수 추가

# 들어오는 간선의 수가 0인 정점을 큐에 넣는다
for i in range(1, n+1):
    if not indegree[i]:
        dq.append(i)

for _ in range(1, n+1):
    target = dq.popleft()

    # 선택한 정점과 연결된 정점의 간선을 삭제한다
    for v in graph[target]:
        indegree[v] -= 1
        if not indegree[v]:
            dq.append(v)

관련 문제들

백준 2252 줄 세우기

백준 1005 ACM Craft

백준 1516 게임 개발

LeetCode Course Schedule

 

내 풀이

백준 1516번 풀이

백준 2252번 풀이

백준 1005번 풀이