위상정렬 알고리즘 (Topological Sort)

yoneeki·2025년 2월 27일

지금 하는 업무가 회계의 재고자산 수불 및 원가 관련한 데이터베이스 업무인데, 단순히 데이터베이스만 만지는 게 아니라, 이 프로그램은 특이하게 회계에 관련된 결과물을 도출해내는 모든 로직이 데이터베이스 프로시저(PL/SQL)로 돌아간다. 정작 프로그램 자체에는 아무것도 없는….

아무튼 재고자산의 수불이란 입고와 출고라는 자산의 이동 방향성이 존재하고 반드시 그 재고 자산이 최종적으로 도착하는 종착이 존재한다. 예를 들자면 당사의 공장에서 생산된 후 당사의 A 지점으로 이동하거나, 혹은 당사의 A 지점에서 판매되어 최종적으로 외부 고객사에 이동하거나 하는 흐름이다. 마지막에는 원가까지 딱 맞아야 하기에 이동 과정에서 비용 및 원가의 변화 역시 제대로 감지해야 한다.

재고자산은 기업이 판매를 목적으로 보유하는 자산이며 원가는 제품(재고자산)을 생산하기 위해 투입된 비용이다.
출고, 납품, 매매가 정상적으로 이루어지기 전까지는 원가는 자산으로 인식되다가 정상적으로 고객에게 판매가 이루어지면 수익이 발생하기 때문에 그제서야 원가는 비용으로 인식된다.

지금까지는 굉장히 복잡한 쿼리로 처리했던 것을 앞으로는 위상 정렬 알고리즘을 통해 처리되도록 로직을 뜯어 고치는 것이 현재의 과제이다. 앞서 말했듯 방향성과 종착점이 존재하는 수불의 특성 상 위상 정렬 알고리즘을 이에 적용하는 것은 적절하다고 볼 수 있다.

시작 전 용어 정리

DAG (Directed Acyclic Graph) : 비순환이며 (시작점과 종점이 존재하고) 유향인(순차적 방향이 존재하는) 그래프.
큐 (Queue) : FIFO (First In First Out)
진입차수 (In-degree) : 특정 노드로 들어오는 간선 개수. 즉 내가 몇 번 참조되냐는 것.
진출차수 (Out-degree) : 특정 노드에서 나가는 간선의 개수. 즉 내가 몇 번 참조하냐는 것.

**a -> b
b -> c
c -> b** 

a 노드의 진입차수:0,  진출차수:1
b 노드의 진입차수:2,   진출차수:1
c 노드의 진입차수:1,   진출차수:1

위상 정렬 알고리즘이란

위상 정렬(Topological Sorting)은 유향 비순환 그래프(DAG, Directed Acyclic Graph)에서 노드들의 선후 관계를 유지하며 나열하는 정렬 알고리즘이다. 일의 순서를 정하거나, 의존 관계가 있는 작업을 처리하는데 사용된다.
순환이 발생하면 위상 정렬 불가능. 따라서 반드시 진입차수가 0인 노드가 존재해야 한다.

위상정렬 방법

진입 차수가 0인 노드를 찾아 큐(Queue)에 삽입
큐에서 노드를 꺼내 해당 노드와 연결된 간선을 제거
간선을 제거한 후, 진입 차수가 0이 된 노드를 다시 큐에 삽입
위 과정을 반복하며 모든 노드를 처리하면 정렬 완료

만약 모든 노드를 방문하기 전에 큐가 비어 있으면 사이클(Cycle)이 존재하는 것.
메모 : 위상정렬에는 DFS(스택 -재귀 사용)나 BFS(큐-진입차수 사용) 두 가지 중 하나의 알고리즘을 사용할 수 있는데 이번 업무에서는 BFS를 채택해 큐를 이용하기로 했다.

위상정렬의 과정 1 : 루트

재고자산의 이동 루트 데이터가 아래와 같다고 하자.

* 출고지 -> 도착지

(1) a -> b
(2) c -> a
(3) d -> a
(4) d -> e
(5) e -> a
(6) e -> c

진입차수가 0인 노드를 큐에 집어 넣고 해당 노드가 있는 루트를 삭제한다.

오른쪽 변을 보면 d가 한 번도 참조되지 않았기에 d의 진입 차수가 0.
Queue : ←——- ( d(1) ) ←———

큐에 d를 넣고 d에 대한 루트는 삭제
(1) a -> b
(2) c -> a
(5) e -> a
(6) e -> c

진입차수가 0인 노드를 큐에 집어 넣고 해당 노드가 있는 루트를 삭제한다.

오른쪽 변을 보면 이미 큐에 들어간 d를 제외하고서는 e가 한 번도 참조되지 않았기에 e의 진입 차수가 0.
Queue : ←——- ( d(1), e(2) ) ←———

큐에 e를 넣고 e에 대한 루트는 삭제
(1) a -> b
(2) c -> a

진입차수가 0인 노드를 큐에 집어 넣고 해당 노드가 있는 루트를 삭제한다.

오른쪽 변을 보면 이미 큐에 들어간 d,e를 제외하고서는 c가 한 번도 참조되지 않았기에 c의 진입 차수가 0.
Queue : ←——- ( d(1), e(2), c(3) ) ←———

큐에 c를 넣고 c에 대한 루트는 삭제
(1) a -> b

진입차수가 0인 노드를 큐에 집어 넣고 해당 노드가 있는 루트를 삭제한다.

오른쪽 변을 보면 이미 큐에 들어간 d,e, c를 제외하고서는 a가 한 번도 참조되지 않았기에 a의 진입 차수가 0.
Queue : ←——- ( d(1), e(2), c(3), a(4) ) ←———

마지막 남은 b가 자동적으로 순번 5

Queue : ←——- ( d(1), e(2), c(3), a(4), b(5) ) ←———

따라서 위상정렬의 결과로 얻은 노드의 방향은 [d→e→c→a→b]

위상정렬의 과정 2 : 코드

직렬연결 된 경우

진입차수가 0이 되는 노드는 항상 하나씩만 생김
큐에는 매번 하나의 데이터만 추가됨

* 출고지 -> 도착지

(1) a -> b
(2) c -> a
(3) d -> a
(4) d -> e
(5) e -> a
(6) e -> c

from collections import deque

# 1️⃣ 그래프 정의 
# (인접 리스트를 값으로 가지는 딕셔너리) 

graph = {
    'a': ['b'],
    'c': ['a'],
    'd': ['a', 'e'],
    'e': ['a', 'c'],
    'b': [],  # 진출 간선이 없는 노드
}

#graph = {
#    'a': ['b'],  
#    'b': ['c'],  # 'b' → 'c' 추가
#    'c': ['a'],  # 'c' → 'a' 추가 (사이클 발생!)
#    'd': ['a', 'e'],
#    'e': ['a', 'c'],
#}

# 2️⃣ 진입 차수(In-degree) 계산
in_degree = {node: 0 for node in graph}  
# 모든 노드의 진입 차수 0으로 초기화
print("*** in_degree : \n", in_degree, "\n")
# { 'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0 }

# 그래프에서 각 노드가 가리키는 노드들의 진입 차수를 계산
for nodes in graph.values():  # 그래프의 모든 값(출발 노드의 도착 노드 리스트)을 순회
    for node in nodes:        # 각 출발 노드에 연결된 개별 도착 노드를 순회
        in_degree[node] += 1  # 도착 노드의 진입 차수 1 증가

print("*** in_degree : \n", in_degree, "\n")
# { 'a': 3, 'b': 1, 'c': 1, 'd': 0, 'e': 1 }

# 3️⃣ 진입 차수가 0인 노드를 큐에 삽입
queue = deque([node for node in in_degree if in_degree[node] == 0])

# 4️⃣ 위상 정렬 수행 (BFS)
topological_order = []  

while queue: 
# 큐가 빌 때까지 반복
# 큐(Queue) 는 현재 진입 차수가 0인 노드들을 저장

    current = queue.popleft()  # 큐에서 노드 하나 꺼내기
    topological_order.append(current)  # 순서에 추가
    
    print("*** topological_order:", topological_order)
    
    print("(", current,"의 도착지) graph[current]:", graph[current])
    
    # 현재 노드와 연결된 간선 제거
    for neighbor in graph[current]:
        
        print("(간선감소전) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
        
        in_degree[neighbor] -= 1  # 진입 차수 감소
        
        print("(간선감소후) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
        
        if in_degree[neighbor] == 0:  # 진입 차수가 0이 되면 큐에 추가
            queue.append(neighbor)
            print("(간선0) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
           
    
    print("*** queue:", queue, "\n")        

# 5️⃣ 출력
print("위상 정렬 순서:", topological_order, "\n")
print("*len(topological_order):", len(topological_order), "\n*topological_order:", topological_order)
print("*len(graph):", len(graph), "\n*graph:", graph)

# 사이클이 있는 경우 감지 
# (위상 정렬 결과의 노드 개수가 원래 노드 개수보다 적으면 사이클 존재)
if len(topological_order) != len(graph):
    print("\n---사이클이 존재하여 위상 정렬이 불가능합니다.---")
else:
    print("\n---위상 정렬 정상 수행---")


###### print result

*** in_degree : 
 {'a': 0, 'c': 0, 'd': 0, 'e': 0, 'b': 0} 

*** in_degree : 
 {'a': 3, 'c': 1, 'd': 0, 'e': 1, 'b': 1} 

*** topological_order: ['d']
( d 의 도착지) graph[current]: ['a', 'e']
(간선감소전) in_degree[neighbor]: 3  / neighbor: a
(간선감소후) in_degree[neighbor]: 2  / neighbor: a
(간선감소전) in_degree[neighbor]: 1  / neighbor: e
(간선감소후) in_degree[neighbor]: 0  / neighbor: e
(간선0) in_degree[neighbor]: 0  / neighbor: e
*** queue: deque(['e']) 

*** topological_order: ['d', 'e']
( e 의 도착지) graph[current]: ['a', 'c']
(간선감소전) in_degree[neighbor]: 2  / neighbor: a
(간선감소후) in_degree[neighbor]: 1  / neighbor: a
(간선감소전) in_degree[neighbor]: 1  / neighbor: c
(간선감소후) in_degree[neighbor]: 0  / neighbor: c
(간선0) in_degree[neighbor]: 0  / neighbor: c
*** queue: deque(['c']) 

*** topological_order: ['d', 'e', 'c']
( c 의 도착지) graph[current]: ['a']
(간선감소전) in_degree[neighbor]: 1  / neighbor: a
(간선감소후) in_degree[neighbor]: 0  / neighbor: a
(간선0) in_degree[neighbor]: 0  / neighbor: a
*** queue: deque(['a']) 

*** topological_order: ['d', 'e', 'c', 'a']
( a 의 도착지) graph[current]: ['b']
(간선감소전) in_degree[neighbor]: 1  / neighbor: b
(간선감소후) in_degree[neighbor]: 0  / neighbor: b
(간선0) in_degree[neighbor]: 0  / neighbor: b
*** queue: deque(['b']) 

*** topological_order: ['d', 'e', 'c', 'a', 'b']
( b 의 도착지) graph[current]: []
*** queue: deque([]) 

위상 정렬 순서: ['d', 'e', 'c', 'a', 'b'] 

*len(topological_order): 5 
*topological_order: ['d', 'e', 'c', 'a', 'b']
*len(graph): 5 
*graph: {'a': ['b'], 'c': ['a'], 'd': ['a', 'e'], 'e': ['a', 'c'], 'b': []}

---위상 정렬 정상 수행---

병렬연결 된 경우

진입차수가 0이 되는 노드가 여러 개일 수도 있음
큐에 한 번에 복수의 데이터가 추가될 때도 있음 → 드디어 큐의 FIFO가 쓸모있음

* 출고지 -> 도착지

(1) a -> b
(2) b -> c
(3) c -> d

from collections import deque

# 1️⃣ 그래프 정의 
# (인접 리스트를 값으로 가지는 딕셔너리) 

graph = {
    'a': ['b', 'c'],
    'b': ['d'],
    'c': ['d'],
    'd': []
}
#graph = {
#    'a': ['b'],  
#    'b': ['c'],  # 'b' → 'c' 추가
#    'c': ['a'],  # 'c' → 'a' 추가 (사이클 발생!)
#    'd': ['a', 'e'],
#    'e': ['a', 'c'],
#}

# 2️⃣ 진입 차수(In-degree) 계산
in_degree = {node: 0 for node in graph}  
# 모든 노드의 진입 차수 0으로 초기화
print("*** in_degree : \n", in_degree, "\n")
# { 'a': 0, 'b': 0, 'c': 0, 'd': 0 }

# 그래프에서 각 노드가 가리키는 노드들의 진입 차수를 계산
for nodes in graph.values():  # 그래프의 모든 값(출발 노드의 도착 노드 리스트)을 순회
    for node in nodes:        # 각 출발 노드에 연결된 개별 도착 노드를 순회
        in_degree[node] += 1  # 도착 노드의 진입 차수 1 증가

print("*** in_degree : \n", in_degree, "\n")
# {'a': 0, 'b': 1, 'c': 1, 'd': 2} 

# 3️⃣ 진입 차수가 0인 노드를 큐에 삽입
queue = deque([node for node in in_degree if in_degree[node] == 0])

# 4️⃣ 위상 정렬 수행 (BFS)
topological_order = []  

while queue: 
# 큐가 빌 때까지 반복
# 큐(Queue) 는 현재 진입 차수가 0인 노드들을 저장

    current = queue.popleft()  # 큐에서 노드 하나 꺼내기
    topological_order.append(current)  # 순서에 추가
    
    print("*** topological_order:", topological_order)
    
    print("(", current,"의 도착지) graph[current]:", graph[current])
    
    # 현재 노드와 연결된 간선 제거
    for neighbor in graph[current]:
        
        print("(간선감소전) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
        
        in_degree[neighbor] -= 1  # 진입 차수 감소
        
        print("(간선감소후) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
        
        if in_degree[neighbor] == 0:  # 진입 차수가 0이 되면 큐에 추가
            queue.append(neighbor)
            print("(간선0) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
           
    
    print("*** queue:", queue, "\n")        

# 5️⃣ 출력
print("위상 정렬 순서:", topological_order, "\n")
print("*len(topological_order):", len(topological_order), "\n*topological_order:", topological_order)
print("*len(graph):", len(graph), "\n*graph:", graph)

# 사이클이 있는 경우 감지 
# (위상 정렬 결과의 노드 개수가 원래 노드 개수보다 적으면 사이클 존재)
if len(topological_order) != len(graph):
    print("\n---사이클이 존재하여 위상 정렬이 불가능합니다.---")
else:
    print("\n---위상 정렬 정상 수행---")


###### print result

*** in_degree : 
 {'a': 0, 'b': 0, 'c': 0, 'd': 0} 

*** in_degree : 
 {'a': 0, 'b': 1, 'c': 1, 'd': 2} 

*** topological_order: ['a']
( a 의 도착지) graph[current]: ['b', 'c']
(간선감소전) in_degree[neighbor]: 1  / neighbor: b
(간선감소후) in_degree[neighbor]: 0  / neighbor: b
(간선0) in_degree[neighbor]: 0  / neighbor: b
(간선감소전) in_degree[neighbor]: 1  / neighbor: c
(간선감소후) in_degree[neighbor]: 0  / neighbor: c
(간선0) in_degree[neighbor]: 0  / neighbor: c
*** queue: deque(['b', 'c']) 

*** topological_order: ['a', 'b']
( b 의 도착지) graph[current]: ['d']
(간선감소전) in_degree[neighbor]: 2  / neighbor: d
(간선감소후) in_degree[neighbor]: 1  / neighbor: d
*** queue: deque(['c']) 

*** topological_order: ['a', 'b', 'c']
( c 의 도착지) graph[current]: ['d']
(간선감소전) in_degree[neighbor]: 1  / neighbor: d
(간선감소후) in_degree[neighbor]: 0  / neighbor: d
(간선0) in_degree[neighbor]: 0  / neighbor: d
*** queue: deque(['d']) 

*** topological_order: ['a', 'b', 'c', 'd']
( d 의 도착지) graph[current]: []
*** queue: deque([]) 

위상 정렬 순서: ['a', 'b', 'c', 'd'] 

*len(topological_order): 4 
*topological_order: ['a', 'b', 'c', 'd']
*len(graph): 4 
*graph: {'a': ['b', 'c'], 'b': ['d'], 'c': ['d'], 'd': []}

---위상 정렬 정상 수행---

사이클이 존재하는 경우

위상정렬 불가능
예를 들어, 'a' → 'b' → 'c' → 'a'와 같이 순환 구조를 만들면 사이클 발생.

from collections import deque

# 1️⃣ 그래프 정의 
# (인접 리스트를 값으로 가지는 딕셔너리) 

#graph = {
#    'a': ['b'],
#    'c': ['a'],
#    'd': ['a', 'e'],
#    'e': ['a', 'c'],
#    'b': [],  # 진출 간선이 없는 노드
#}

graph = {
    'a': ['b'],  
    'b': ['c'],  # 'b' → 'c' 추가
    'c': ['a'],  # 'c' → 'a' 추가 (사이클 발생!)
    'd': ['a', 'e'],
    'e': ['a', 'c'],
}

# 2️⃣ 진입 차수(In-degree) 계산
in_degree = {node: 0 for node in graph}  
# 모든 노드의 진입 차수 0으로 초기화
print("*** in_degree : \n", in_degree, "\n")
# { 'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0 }

# 그래프에서 각 노드가 가리키는 노드들의 진입 차수를 계산
for nodes in graph.values():  # 그래프의 모든 값(출발 노드의 도착 노드 리스트)을 순회
    for node in nodes:        # 각 출발 노드에 연결된 개별 도착 노드를 순회
        in_degree[node] += 1  # 도착 노드의 진입 차수 1 증가

print("*** in_degree : \n", in_degree, "\n")
# {'a': 3, 'b': 1, 'c': 2, 'd': 0, 'e': 1} 

# 3️⃣ 진입 차수가 0인 노드를 큐에 삽입
queue = deque([node for node in in_degree if in_degree[node] == 0])

# 4️⃣ 위상 정렬 수행 (BFS)
topological_order = []  

while queue: 
# 큐가 빌 때까지 반복
# 큐(Queue) 는 현재 진입 차수가 0인 노드들을 저장

    current = queue.popleft()  # 큐에서 노드 하나 꺼내기
    topological_order.append(current)  # 순서에 추가
    
    print("*** topological_order:", topological_order)
    
    print("(", current,"의 도착지) graph[current]:", graph[current])
    
    # 현재 노드와 연결된 간선 제거
    for neighbor in graph[current]:
        
        print("(간선감소전) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
        
        in_degree[neighbor] -= 1  # 진입 차수 감소
        
        print("(간선감소후) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
        
        if in_degree[neighbor] == 0:  # 진입 차수가 0이 되면 큐에 추가
            queue.append(neighbor)
            print("(간선0) in_degree[neighbor]:", in_degree[neighbor], " / neighbor:", neighbor)
           
    
    print("*** queue:", queue, "\n")        

# 5️⃣ 출력
print("위상 정렬 순서:", topological_order, "\n")
print("*len(topological_order):", len(topological_order), "\n*topological_order:", topological_order)
print("*len(graph):", len(graph), "\n*graph:", graph)

# 사이클이 있는 경우 감지 
# (위상 정렬 결과의 노드 개수가 원래 노드 개수보다 적으면 사이클 존재)
if len(topological_order) != len(graph):
    print("\n---사이클이 존재하여 위상 정렬이 불가능합니다.---")
else:
    print("\n---위상 정렬 정상 수행---")

#### print result 
*** in_degree : 
 {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0} 

*** in_degree : 
 {'a': 3, 'b': 1, 'c': 2, 'd': 0, 'e': 1} 

*** topological_order: ['d']
( d 의 도착지) graph[current]: ['a', 'e']
(간선감소전) in_degree[neighbor]: 3  / neighbor: a
(간선감소후) in_degree[neighbor]: 2  / neighbor: a
(간선감소전) in_degree[neighbor]: 1  / neighbor: e
(간선감소후) in_degree[neighbor]: 0  / neighbor: e
(간선0) in_degree[neighbor]: 0  / neighbor: e
*** queue: deque(['e']) 

*** topological_order: ['d', 'e']
( e 의 도착지) graph[current]: ['a', 'c']
(간선감소전) in_degree[neighbor]: 2  / neighbor: a
(간선감소후) in_degree[neighbor]: 1  / neighbor: a
(간선감소전) in_degree[neighbor]: 2  / neighbor: c
(간선감소후) in_degree[neighbor]: 1  / neighbor: c
*** queue: deque([]) 

위상 정렬 순서: ['d', 'e'] 

*len(topological_order): 2 
*topological_order: ['d', 'e']
*len(graph): 5 
*graph: {'a': ['b'], 'b': ['c'], 'c': ['a'], 'd': ['a', 'e'], 'e': ['a', 'c']}

---사이클이 존재하여 위상 정렬이 불가능합니다.---

즉 진입차수가 0인 노드가 없는 구간이 발생하여 모든 노드를 참조하기 이전에 와일문이 종료되면 사이클 즉 순환참조가 발생했다고 보는 것.
이제 문제는 이걸 데베쿼리로 어떻게 구현하나…

yoneeki

Working Abroad ...

이전 포스트

GraphAPI

다음 포스트