[Python] 줄 세우기 - 위상 정렬

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

생각과정

- 방향이 있고, 사이클이 없는 그래프의 노드들을 정렬한다 -> 위상 정렬

 

 

구현

init = input().split()
n = int(init[0])
m = int(init[1])
arr = [[] for i in range(n)]
degree = [0 for i in range(n)]
for i in range(m):
    l = list(map(int, input().split()))
    arr[l[0]-1].append(l[1]-1)
    degree[l[1]-1]+=1


from collections import deque
def solution(n, degree, arr):
    result = []
    queue = deque([])
    # 시작 노드 초기값으로 넣기
    for i, d in enumerate(degree):
        if d == 0:
            queue.append(i+1)
    while len(queue) > 0:
        q = queue.popleft()
       # print(q, queue, degree, arr[q-1])
        result.append(q)
        for a in arr[q-1]:
            degree[a] -= 1
            if degree[a] == 0:
                queue.append(a+1)

    print(' '.join(list(map(str, result))))

solution(n, degree, arr)

 

결과

 

위상정렬 (Kahn's Algorithm)

1) 그래프를 만들 때, 각 노드에서 출발하는 간선 중 도착하는 노드들을 저장한다.

2) outbound 간선 수를 노드별로 degree 배열에 저장한다.

3) 시작 노드를 저장할 큐를 만들고, 초기 시작 노드들을 넣는다. 이때, 시작 노드는 degree가 0인 노드이다.

4) 큐가 빌 때까지 반복해서 꺼낸다. 꺼낸 노드에서 연결되는 다른 노드가 있다면 degree를 1씩 감소시킨다. degree를 감소시키는 작업은 간선 배열에서 검사한 간선을 제거하는 것을 대신한다. 

5) degree가 0이라면 시작 노드에 해당하므로 큐에 추가한다.

 

참고

www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

Kahn's algorithm for Topological Sorting - GeeksforGeeks

snoop-study.tistory.com/46

Topological Sort(위상 정렬) 정리