위상 정렬(그래프 정렬)

Chooooo·2023년 2월 15일

문제 유형 위상정렬

알고리즘 활용하는 문제 유형들

목록 보기

22/33

위상정렬

위상정렬이란, 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다.

간선이 방향성을 가진 그래프여야 한다.
그래프 내부에 순환(cycle)이 없어야 한다. 각각의 일의 선후관계가 복잡하게 얽혀있을 때 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘이다.

⚽ 위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘이라고 이해하자.

위상정렬의 대표적인 예로 대학교의 선수과목 구조를 들 수 있다. 간단하게 말하면 B를 하기 위해 A라는 작업을 먼저 해야 하는 구조가 있을 때, 그 작업 순서를 구해주는 것이 위상 정렬이다.

위상정렬은 여러 개의 답이 존재한다.

😀 위상정렬의 시간복잡도는 O(V+E)이다.

실제 위상정렬 알고리즘을 다루기 전에 먼저 간단히 그래프 관련 자료구조에서 자주 등장하는 개념인 진입차수(Indegree), 진출차수(Outdegree)에 대해서 알아보자

그래프는 노드와 간선으로 구성되는데,

진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다.
진출차수는 특정한 노드에서 나가는 간선의 개수를 의미한다.

👻 개념을 확인했으니 위상정렬에 대해서 공부해보자.

위상정렬 알고리즘

위상정렬은 DFS를 이용해서 구현할 수도 있으며, 큐를 이용해서 구현할 수도 있다.

큐를 이용하는 위상정렬에 대해서 알아보자.
방향그래프 인접행렬을 입력받으면서 그래프화를 시킬텐데 같이 진입차수 1차원 리스트를 구해준다.
진입차수 리스트를 만든 후에 그 값이 0이라는 것은 먼저 해야할 작업이 0개라는 뜻이고 degree값이 1이면 먼저 해야할 작업이 1개 있다는 뜻이다.
그렇기에 진입차수가 0인 것부터 큐에 넣어준 후에 이제 그 노드부터 시작하면 돼 !

동작과정

진입 차수가 0인 정점을 큐에 삽입한다.
큐에서 원소를 꺼내 해당 원소에 연결된 간선을 제거한다. (degree 값을 줄이는거지)
간선을 제거한 후 진입 차수가 0이 된 정점을 큐에 삽입한다.
위 과정을 반복한다.

😀 만약 모든 정점을 방문하기 전에 큐가 비게 된다면 사이클이 존재하는 것이다. 큐에서 원소를 꺼낸 순서가 위상 정렬의 결과가 된다 !

⚽ 정점과 진입차수를 저장한 그래프를 만들어주고, 진입차수가 0인 정점 1을 큐에 삽입한다.

⚽ 정점1에 연결된 간선을 제거한 후, 진입차수가 0이 된 정점 2를 큐에 삽입한다.

⚽ 정점2에 연결된 간선 제거 후, 진입차수가 0이 된 정점 3을 큐에 삽입한다.

⚽ 계속 반복해주면 1→2→3→4→5의 순서로 위상 정렬이 된다 !

위상정렬 알고리즘 코드

import sys
import itertools as it   #이것이 순열이나 조합 자동으로 구해주는 라이브러리야!
from collections import deque
import heapq as heap   #heap이라는 이름으로 사용할꺼야
sys.stdin = open("input.text", "rt")

#노드의 개수와 간선의 개수 입력받기
v,e = map(int, input().split())
#모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v+1)
#각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v+1)]

#방향 그래프의 모든 간선 정보를 입력 받기
for _ in range(e):
    a,b = map(int, input().split())
    graph[a].append(b)  #정점 a에서 b로 이동가능 --> 인접노드 추가하는 과정이야.
    #진입차수 1증가
    indegree[b] +=1 #a에서b로 이동이 가능하다는 것은
    #노드 b에 대해서 들어오는 간선이 존재한다는 것이기에 진입차수 1 증가.

#위상정렬함수
def toplogy_sort():
    result = []  #알고리즘 수행 결과를 담을 리스트
    q = deque()  #큐 기능을 위해 라이브러리.
    #처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1,v+1):
        if indegree[i] == 0:
            q.append(i)
    #큐가 빌 때까지 반복
    while q:
        #큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)    #큐에 들어간 순서가 전체 위상정렬 수행된 결과와 동일하기에 큐에서 원소 꺼낼때마다 리스트에 담아야지.

        #해당 원소와 연결된 노드(인접노드)들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1   #즉 나가는 간선을 제거하는거야.
            #새롭게 진입차수가 0이되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)
    #위상정렬 수행 결과
    for i in result:
        print(i, end = " ")

toplogy_sort()

다시 정리해본 코드

import sys
from collections import deque
sys.stdin = open("input.text", "rt")


# 노드의 개수와 간선의 개수 입력
n,m = map(int ,input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (n+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
g = [[] for _ in range(n+1)] # 1번 인덱스부터 사용

# 방향 그래프의 모든 간선 정보 입력 받기
for _ in range(m):
    a,b = map(int, input().split())
    g[a].append(b) # 정점 a -> b로 이동 가능
    # 연결할 때마다 진입차수 증가
    indegree[b] += 1
    # b로 들어오는 간선 (진입차수) + 1

# 여기까지 기본 세팅

# 위상정렬 함수
def toplogy_sort():
    result = [] #결과 리스트
    dq = deque()
    # 처음 시작할 때 진입차수가 0인 노드를 큐에 삽입
    for v in range(1,n+1):
        if indegree[v] == 0:
            dq.append(v)

    # 큐가 빌 떄까지 반복
    while dq:
        # 큐에서 원소 꺼내기
        now = dq.popleft()
        result.append(now) # 큐에 들어간 순서가 전체 위상정렬 수행된 결과와 동일하기에
        # 큐에서 원소 꺼낼 때마다 리스트에 담으면 돼 ( 그 결과가 위상정렬 결과 )
        # 현재 노드와 연결된 노드(인접노드)들의 진입차수 1 빼기
        for v in g[now]: # v는 now(현재노드)의 인접노드들
            indegree[v] -= 1
            if indegree[v] == 0:
                dq.append(v)

    # 위상정렬 수행결과
    # print(*result)
    for x in result:
        print(x, end = " ")
        
        
toplogy_sort()

문제 유형을 보면서 이해해보자

위상정렬(그래프 정렬)

위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘입니다.
각각의 일의 선후관계가 복잡하게 얽혀있을 때 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘입니다.
만약 아래와 같은 일의 순서를 각각 지키면서 전체 일의 순서를 정한다면
1 4 //1번일을 하고 난 후 4번일을 해야한다.
5 4
4 3
2 5
2 3
6 2

전체 일의 순서는 1, 6, 2, 5, 4, 3과 같이 정할 수 있다. 전체 일의 순서는 여러 가지가 있습니다 그 중에 하나입니다.

▣ 입력설명
첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어집니다.
두 번째 줄부터 M개의 정보가 주어집니다.

▣ 출력설명
전체 일의 순서를 출력합니다.

▣ 입력예제 1
6 6
1 4
5 4
4 3
2 5
2 3
6 2

▣ 출력예제 1
1 6 2 5 4 3

import sys
sys.stdin = open("input.text", "rt")
# input = sys.stdin.readline
from collections import deque

n,m = map(int, input().split())
g = [[0] * (n+1) for _ in range(n+1)]
degree = [0] * (n+1) #진입차수
dq = deque()

for i in range(m): #간선
    a,b = map(int, input().split()) #방향 그래프 !!!
    g[a][b] = 1
    degree[b] += 1 #진입차수 a->b니까 b값을 올려야지

for i in range(1,n+1):
    if degree[i] == 0: #진입차수가 0이면
        dq.append(i) #진입차수가 0이라는 것은 선행해야 하는 작업이 없다는 것이다.

while dq:
    x = dq.popleft()
    print(x, end = " ") #여기서 출력한다는 것은 x 작업을 했다는 뜻 !
    #x의 작업을 했으니 이제 진입차수를 제거해줘야해
    for i in range(1,n+1):
        if g[x][i] == 1: #만약 x에서 흐르다면...
            degree[i] -= 1
            if degree[i] == 0:
                dq.append(i)

인접 리스트로

import sys
from collections import deque
sys.stdin = open("input.text", "rt")


n,m = map(int ,input().split()) # 일의 개수, 일의 순서 정보
indegree = [0] * (n+1) # 진입차수
g = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int ,input().split())
    g[a].append(b)
    indegree[b] += 1

# 기본 세팅

def toplogy_sort():
    res = [] # 결과 리스트
    dq = deque()
    for v in range(1,n+1):
        if indegree[v] == 0:
            dq.append(v)

    while dq:
        now = dq.popleft()
        res.append(now)

        for v in g[now]:
            indegree[v] -= 1
            if indegree[v] == 0:
                dq.append(v)

    print(*res)
toplogy_sort()