위상 정렬 개념 & 알고리즘 문제풀이 (백준 2637 장난감 조립, 2252 줄세우기 [파이썬])

위상 정렬(topological)

유향 그래프에서 정점(vertex)를 간선(edge)의방향에 거스르지 않도록 나열하는 것을 의미함.

선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따른 정렬에 사용될 수 있는데, 대표적으로 대학교 수강과목에서 선수과목 구조를 예를 들 수 있다. 선수과목이 있다면 선수과목을 먼저 수강해야하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 이용할 있기 때문이다.

 

위상 정렬 성립조건

• 유향 그래프 구조일 것 (directed)
  간선들이 방향을 가지고 있어야 한다. 유향 그래프 구조에 따라 2개 이상의 정렬이 나올 수 있다.
• 싸이클을 형성하지 않을 것 (acyclic graph)
  싸이클이 형성된다는 것은 순환구조를 의미한다. 순환하는 구조에서는 위상정렬이 불가능하다.

Directed / Acyclic

 

위상 정렬 알고리즘을 위해 알아야할 개념(쉬움)

• 진입 차수(Indegree) - 특정한 노드로 들어오는 간선의 개수
• 진출 차수(Outdgree) - 특정한 노드에서 나가는 간선의 개수

위상정렬 알고리즘 구현방법은 2가지가 있다. 

1. 스택을 활용한 DFS를 통한 위상 정렬
2. 큐를 사용한 위상 정렬
   진입차수가 0인 모든 노드를 큐에 넣는다.
   큐가 빌 때까지 다음의 과정을 반복한다.
   1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
   → 결과 위상정렬이 됨
   → 만약에 모든 노드 방문 전에 큐가 빈다면, 사이클이 존재한다고 판단할 수 있다. 사이클에 포함된 어떤 원소도 큐에 들어갈 수 없기 때문임.

 

위상 정렬 알고리즘은 차례대로 모든 노드를 확인하며 간선을 제거해나가야 하기 때문에, 시간복잡도 O(V+E)이다.

 

 

문제 예시 1. 백준 - 줄 세우기

위상정렬의 기초 문제이다. 입력 받는 값을 이용해 그대로 위상정렬 알고리즘에 넣으면 간단히 풀린다.

전체 그룹에서 일부 학생들의 키를 비교한 데이터를 이용해 데이터를 정렬하는 문제다.

'일부' 학생들의 키를 비교한 것이기 때문에 정답이 다양할 수 있다.

 

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

2252번: 줄 세우기

# 큐를 이용한 위상정렬
from collections import deque
import sys
input=sys.stdin.readline
v, e= map(int,input().split())
E=[[] for _ in range(v+1)] # 간선 리스트 

indegree = [0] * (v+1) # 각 노드의 진입차수 기록

for _ in range(e):
    a, b = map(int, input().split())
    E[a].append(b)   # a에서 b로 뻗은 간선 표현
    indegree[b]+=1   # 노드 b 로 진입하는 간선 추가.


def topology_sort():
    result = [] #결과 리스트
    q=deque()

    for i in range(1,v+1):
        if indegree[i]==0:
            q.append(i)


    while q:
        x=q.popleft()
        result.append(x)  # 위상정렬 순서대로 결과값 입력
        for i in E[x]:
            indegree[i]-=1
            if indegree[i]==0:
                q.append(i)
    
    for i in result:
        print(i, end=' ')

topology_sort()

 

문제 예시 2. 백준 - 장난감 조립

문제풀이 핵심

1. 진입차수 계산을 통한 기본부품 파악 ( 기본 부품의 경우 진입차수가 0임 )

2. 위상정렬을 통해 어떤 부품(기본 부품 혹은 중간 부품)이 어떤 부품(중간 부품 혹은 완제품)에 속하는지 정렬하고, 기본 부품과 가장 가까운 하위 레벨 부터 순차적으로 연산하는 것이다.  가장 하위 레벨부터 풀어나간다면 중간 부품을 더 낮은 단위로 다시 분해해서 연산해야하는 부담을 줄일 수 있다.

 

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

2637번: 장난감 조립

import sys
from collections import deque
input=sys.stdin.readline
#입력값 받기 
N=int(input()) #부품 수 N이 완제품
V=int(input()) #간선 수
E=[[] for _ in range(N+1)] #연결정보.
indegree=[0]*(N+1) #부품별 진입차수 0일 경우 기본부품.
needs=[[0]*(N+1) for _ in range(N+1)] #각 부품이 기본부품 얼마나 필요한지 Matrix

for i in range(V):
    a,b,c = map(int,input().split())
    E[b].append([a,c])  #a만드는데 b가 c개 필요.
    indegree[a]+=1      #진입차수 정보모음

q=deque()
basic_parts=[]
for i in range(1,N+1):
    if indegree[i]==0:
        basic_parts.append(i) #기본부품 리스트
        q.append(i)

while q:
    now=q.popleft()
    for object, n in E[now]:
        if now in basic_parts:   # 기본부품일경우 목적제품에 +n개
            needs[object][now]+=n
        else:
            for i in range(1,N+1):
                needs[object][i]+=needs[now][i]*n
        indegree[object]-=1
        if indegree[object]==0:
            q.append(object)

for i in range(N+1):
    if needs[N][i] > 0:
        print(i,needs[N][i])

#위랑 같은 표현
# for x in enumerate(needs[N]):
#     if x[1]>0:
#         print(*x)