위상 정렬(Topology Sort), boj(백준) 2252번 예시

위상 정렬(Topology Sort)

• 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다.

• 조건으로 해석 sw사관학교 정글을 수료하기 위해 신청을 해야하며 시험과 면접을 통과해야 하고 입소 후 주어진 과제들에 열심히 참여하여야(주100시간 밥먹고 똥싸고 개발만하기) 정글을 수료할 수 있다.위상 정렬 특징
• 사이클이 발생하지 않는 방향 그래프이다.
  • DAG : Direct Acyclic Graph : 사이클이 없는 방향 그래프
  • 시작점이 존재해야 한다. (전위차수 0)
• 위상 정렬은 스택이나 큐를 이용한다.
• 시간 복잡도 : O(V+E)

위상 정렬 알고리즘 동작 과정

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다.

위상 정렬 후 결과 : 1->2->5->3->6->4->7 OR 1->5->2->3->6->4->7 둘 다 가능

큐를 사용한 위상정렬 백준(boj) 2252번 예시

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
# 진입 차수 배열
indegree=[0]*(n+1)
# 그래프 배열 
graph=[[] for _ in range(n+1)]

# 그래프, 진입 차수 배열 만들기
for i in range(m):
    u,v=map(int,input().split())
    graph[u].append(v)
    # v: 화살표 받는 노드, 진입 차수 1증가
    indegree[v]+=1

# 큐 생성
q=deque()

for i in range(1,n+1):
    # 위상정렬이 0일 때 큐에 추가 
    if indegree[i]==0:
        q.append(i)

while q:
    x=q.popleft()
    print(x,end=' ')
    for i in graph[x]:
        indegree[i]-=1
        if indegree[i]==0:
            q.append(i)