[Algorithm] - 위상 정렬

위상 정렬

---

방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬
싸이클이 존재하는 경우는 발생할 수 없다

 

• 일반적으로 방향그래프로 설정이 되어 있기 때문에 Indegree 값이 0인 Node들에서 먼저 시작하면서 VFS 처럼 구현하면 된다.
• 위상 정렬의 결과가 Node들의 수와 동일해야 한다! ( 동일하지 않는 경우는 Cycle이 발생된 경우 )

 

알고리즘

시간 복잡도 : O( V+E )

1. 처음 방향 그래프들의 Edge를 읽으며, Indegree Table을 설정

2. Indegree가 0인 Node들을 Queue에 넣는다.

3. Queue에 Node들을 꺼내며, 위상 정렬 값 추가

4. 연결된 Node들의 Indgree값을 줄여주고 , 0이면 Queue에 추가

5. 3~4반복

# 위상 정렬
# 그래프를 사용
# Indgree의 값을 보고 판단
'''
7 7
A B
D B
C B
C D
D E
E F
G E
'''
import sys
from collections import deque
input = sys.stdin.readline

n , m = map ( int , input().split() )
adj = [ [] for _ in range( m ) ]
indgree = [0]*m
queue = deque()
answer = []

for _ in range( n ) :
    start , end = map ( str , input().split() )
    adj[ord(start)-65].append(ord(end)-65)
    indgree[ord(end)-65] += 1

for index , graph in enumerate(indgree) :
    if not graph :
        queue.append(index)

while ( queue ) :
    temp = queue.popleft()
    answer.append(chr(temp+65))
    for data in adj[temp] :
        indgree[data] -= 1
        if not indgree[data] :
            queue.append(data)

print (answer)

 

BOJ 2252번 - 줄 세우기

---

• 선후관계 처리가 필요함에 따라 위상 정렬로 풀어야 한다.

# BOJ 2252번 - 줄 세우기
# Idea - 두 학생의 키를 보고 정렬 시켜야 한다.
# Edge = 선후 관계 -> 위상 정렬

import sys
from collections import deque
input = sys.stdin.readline

n , m = map( int , input().split() )
adj = [[] for _ in range( n+1 )]
indegree = [0] * (n+1)
queue = deque()
answer = []

for _ in range( m ) :
    small , big = map ( int , input().split() )
    adj[small].append(big)
    indegree[big] += 1

for index , data in enumerate ( indegree[1:] ) :
    if not data :
        queue.append(index+1)

while ( queue ) :
    temp = queue.popleft()
    answer.append(temp)
    for data in adj[temp] :
        indegree[data] -= 1
        if not indegree[data] :
            queue.append(data)
    
[print(temp) for temp in answer]

 

프로그래머스 - 순위

---

• 위상정렬 문제인듯 보이지만, 단순 그래프 구현 문제이다.