위상정렬

개념

사이클이 없는 방향 그래프에서 차례로 수행해야 할 순서를 결정해주기 위해 사용하는 알고리즘

관련문제

https://www.acmicpc.net/problem/2252

구현과정

1. 모든 정점의 indegree(노드에서 들어오는 간서의 갯수)를 설정
2. indegree가 0인 정점들을 큐에 추가
3. 큐가 빌때까지 아래의 과정 반복
   1.큐의 앞요소 꺼내기
   2.꺼낸 요소의 인접한 노드들의 indegree값을 1 감소
   3.인접한 노드들의 indegree값이 0일 경우 큐에
   (만약 그래프에 사이클이 존재한다면 사이클 노드에서 indegree값은 1이상이므로 큐에 추가X)

결론:자신에게 들어오는 노드들의 방문이 끝난 후 처리를 함으로서 순서를 결정한다.

시간복잡도

초기 큐에 indegree값이 0인 노드를 찾는 과정(V)+indegree값이 0일때만 큐에 추가하는 방식이기 때문에 노드의 갯수(E)=O(V+E)

코드

from collections import deque

v,e=map(int,input().split())

#각 노드들로 들어오는 노드의 갯수 초기화
indegree=[0 for _ in range(v+1)]
#그래프 초기화
graph=[[] for _ in range(v+1)]

for i in range(e):
    a,b=map(int,input().split())
    graph[a].append(b)
    #받는 노드의 갯수 추가
    indegree[b]+=1

result=[]
to_do_list=deque([(i,0) for i in range(1,v+1) if indegree[i]==0])
while len(to_do_list)>0:
    do,depth=to_do_list.popleft()
    #순서 추가
    result.append((do,depth))
    #인접노드들 방문
    for to_do in graph[do]:
        #인접노드 입장에서 do를 이미 방문했으므로 들어오는 노드 갯수 감소
        indegree[to_do]-=1
        #들어오는 노드 갯수가 모두 완료 되었을때 해당 노드 추가
        if indegree[to_do]==0:
            to_do_list.append((to_do,depth+1))

print(result)

예시

설명

다음은 서울대학교의 컴퓨터공학과 커리큘럼이다.

이미 잘 정리되어 있지만 학년의 구분 없이 병행학습을 할 때의 순서를 뽑기위해 위상정렬 알고리즘을 써서 단계별로 출력해보자.

예시코드

e=int(input())

indegree={}
graph={}

for i in range(e):
    a,b=input().split()
    if a not in graph:
        graph[a]=[]
    if b not in graph:
        graph[b]=[]
    graph[a].append(b)
    
    if a not in indegree:
        indegree[a]=0
    if b not in indegree:
        indegree[b]=0
    indegree[b]+=1
    
result=[]
to_do_list=deque()
for key,value in indegree.items():
    if value==0:
        to_do_list.append((key,0))
        
while len(to_do_list)>0:
    do,depth=to_do_list.popleft()
    result.append((do,depth))
    for to_do in graph[do]:
        indegree[to_do]-=1
        if indegree[to_do]==0:
            to_do_list.append((to_do,depth+1))
for i in range(depth+1):
    print("depth==========",i,"==================")
    for subjects,depth in result:
        if depth==i:
            print(subjects)

입력

29
이산수학 오토마타이론
이산수학 자료구조
이산수학 데이터통신
컴퓨터프로그래밍 프로그래밍의원리
컴퓨터프로그래밍 소프트웨어개발의원리와실습
컴퓨터프로그래밍 자료구조
프로그래밍의원리 프로그래밍언어
소프트웨어개발의원리와실습 소프트웨어공학
오토마타이론 컴파일러
자료구조 데이터마이닝개론
자료구조 알고리즘
자료구조 데이터베이스
자료구조 인공지능
자료구조 데이터통신
자료구조 컴퓨터그래픽스
데이터통신 컴퓨터네트워크
공학수학1 선형및비선형계산모델
공학수학1 공학수학2
공학수학1 전기전자회로
논리설계 전기전자회로
논리설계 컴퓨터구조
선형및비선형계산모델 컴퓨터그래픽스
선형및비선형계산모델 딥러닝의기초
공학수학2 딥러닝의기초
공학수학2 디지털신호처리
전기전자회로 하드웨어시스템설계
컴퓨터구조 하드웨어시스템설계
컴퓨터구조 시스템프로그래
시스템프로그래 운영체제

출력

depth========== 0 ==================
이산수학
컴퓨터프로그래밍
공학수학1
논리설계
depth========== 1 ==================
오토마타이론
프로그래밍의원리
소프트웨어개발의원리와실습
자료구조
선형및비선형계산모델
공학수학2
전기전자회로
컴퓨터구조
depth========== 2 ==================
컴파일러
프로그래밍언어
소프트웨어공학
데이터마이닝개론
알고리즘
데이터베이스
인공지능
데이터통신
컴퓨터그래픽스
딥러닝의기초
디지털신호처리
하드웨어시스템설계
시스템프로그래
depth========== 3 ==================
컴퓨터네트워크
운영체제

해석

depth를 month라 할때 해당 달마다 포함되는 모든 과목들을 공부하면 순서대로 달에 해당하는 과목들을 학습할 수 있게된다.