[그래프] 위상 정렬 (어렵지 않다! 클릭클릭!)

위상정렬 topology sort

 

처음에 이 용어를 들었을 때는 공부할 엄두조차 나지 않았다.

너무 어려워보였기 때문이다 ㅋㅋㅋㅋㅋ

요 며칠 그래프 공부하면서 느낀건데 난 공부해보기도 전에 지레짐작하고 쫄아버리는 경향이 없잖아 있는거같닼ㅋㅋㅋ

위상정렬은 b가 나오기 전에 반드시 a가 나와야된다 라는 규칙이 있을 때 이 규칙을 어기지 않고 원소를 나열하는 방법을 말한다. 원소가 2개일 때야 a, b 이렇게 나열하면 되지만 원소가 많아지고 그 사이의 관계가 복잡해지기 시작하면 직관적으로 나열하긴 힘들것이다. 이때 위상정렬이 쓰인다.

 

위상정렬을 사용하기 가장 좋은 예는 '선수 과목' 문제다. CS지식을 공부하려는 학생이 있다. 근데 과목이 너무 많고 선수 관계가 복잡하게 얽혀있다. (ex : 자료구조 먼저 배우고 알고리즘을 배워야 한다) 이 때 이 학생이 선-후 관계를 지키면서 CS지식을 공부하려면 어떤 순서로 공부해야 할까?

 

위상정렬은 a부터 나오고 b가 나와야 된다는 관계를 노드 a로부터 노드 b로 간선이 이어져있는 것으로 표현한다. 그렇다. 그래프다. 그럼 위상정렬이 어떻게 수행되는지 알아보자. 정말 간단하다.

1. 최초에 시작노드를 큐에 집어넣는다.

2. 큐가 빌 때까지 반복한다.

(1) 큐에서 pop하고 이를 결과 리스트에 넣는다. (큐에서 노드를 pop하는 순서가 정답이 된다.)

(2) 현재 노드에서 다른 노드로 연결된 간선을 모두 제거하고 indegree가 0인 노드를 큐에 넣는다.

indegree는 노드로 들어오는 간선의 개수를 말한다. indegree가 0이면 선수 노드가 없다는 것이며 그 노드에서부터 시작해도 괜찮다는 것.

3. 만약 노드 사이에 사이클이 있으면 사이클이 있는 노드들은 indegree가 0이 될 수 없어서 모든 노드를 방문하기 전에 큐가 비어버릴 것이다. 이를 이용해 사이클 판별이 가능하다.

 

indegree 리스트를 따로 만들면 구현이 편해진다.

2-2는 graph[현재노드] 리스트를 순회하면서 연결된 노드들의 indegree를 1씩 낮추는 방법으로 수행이 가능하다. 1씩 낮춘후에 0이 되면 큐에 넣으면 된다. 그리고 graph[현재노드] = []로 바꿈으로써 간선 제거 작업이 완료된다.

 

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

q = deque()
q.append(1)
count = 0

while q:
    current = q.popleft()
    print(current, end=' ')
    count += 1

    for nxt in graph[current]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            q.append(nxt)
    
    graph[current] = []

print()

if count == v:
    print("NO CYCLE")
else:
    print("CYCLE")

 

쉽네!