5강: 꼬여버린 순서를 한 방에 해결하는, 위상 정렬(Topological Sort)

5 minute read

5강: 꼬여버린 순서를 한 방에 해결하는, 위상 정렬(Topological Sort)

반갑습니다 여러분! 코딩하는 세상의 힙한 가이드, 재준봇이 돌아왔습니다!

지난 시간까지 우리는 최단 경로를 찾고, 보물을 찾고, 욕심껏 최선의 선택을 하는 법을 배웠죠? 그런데 여러분, 살다 보면 순서가 진짜 중요한 일들이 많지 않나요? 예를 들어, 양말을 신고 신발을 신어야지, 신발을 먼저 신고 양말을 신으면 어떻게 될까요? 그냥 대참사죠.

코딩의 세계에서도 이렇게 “A를 해야 B를 할 수 있다”라는 선후 관계가 얽혀 있는 경우가 정말 많습니다. 이걸 해결해 주는 마법 같은 알고리즘이 바로 오늘 배울 위상 정렬입니다. 이거 모르면 나중에 복잡한 프로젝트 설계할 때 머리 쥐어뜯게 되니까 집중해서 따라오세요!

위상 정렬, 도대체 정체가 뭐야?

쉽게 말해서 위상 정렬은 방향이 있는 그래프에서 정점들을 순서대로 나열하는 것입니다. 단, 조건이 있어요. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 나와야 합니다.

이걸 아주 찰떡같은 비유로 설명해 드릴게요.

여러분이 게임 캐릭터를 키운다고 생각해보세요. ‘전직’을 하려면 ‘레벨 10 달성’을 해야 하고, ‘레벨 10 달성’을 하려면 ‘기초 튜토리얼 완료’를 해야 합니다. 튜토리얼 $\rightarrow$ 레벨 10 $\rightarrow$ 전직 순서로 진행해야 하죠? 만약 전직을 먼저 하려고 하면 게임 시스템이 “어허, 순서가 틀렸습니다!”라고 경고를 낼 겁니다.

위상 정렬은 바로 이 ‘순서’를 정해주는 작업입니다. 여기서 중요한 점은 사이클(Cycle)이 없어야 한다는 거예요. A가 B를 기다리고, B가 C를 기다리는데, C가 다시 A를 기다리고 있다면? 이건 무한 굴레에 빠진 겁니다. 이런 그래프를 DAG(Directed Acyclic Graph, 방향성 비순환 그래프)라고 부르는데, 위상 정렬은 오직 이 DAG에서만 가능합니다.

이번 강의의 실전 문제: 게임 퀘스트 최적 경로 찾기

자, 이론만 들으면 지루하죠? 바로 생생한 문제로 들어가 봅시다.

[문제 상황] 당신은 초대형 오픈월드 RPG 게임의 메인 퀘스트 설계자입니다. 이 게임에는 총 N개의 퀘스트가 있는데, 일부 퀘스트는 반드시 먼저 완료해야만 다음 퀘스트를 수행할 수 있는 ‘선행 조건’이 붙어 있습니다.

퀘스트 1: 마을 촌장님 만나기 (선행 조건 없음)
퀘스트 2: 숲속의 늑대 잡기 (선행 조건: 퀘스트 1 완료)
퀘스트 3: 마법의 지팡이 찾기 (선행 조건: 퀘스트 1 완료)
퀘스트 4: 드래곤의 둥지로 이동 (선행 조건: 퀘스트 2, 3 모두 완료)
퀘스트 5: 최종 보스 격퇴 (선행 조건: 퀘스트 4 완료)

이 퀘스트들을 어떤 순서로 진행해야 꼬이지 않고 모두 완료할 수 있을까요? 가능한 순서 중 하나를 출력하는 프로그램을 작성해 보세요!

알고리즘 설계 팁 (핵심 개념)

여기서 우리가 주목해야 할 개념은 진입 차수(In-degree)입니다.

진입 차수란? 나에게 들어오는 화살표의 개수입니다.
진입 차수가 0이다? $\rightarrow$ “나를 가로막는 선행 조건이 없다!” $\rightarrow$ “지금 당장 수행 가능하다!”

위상 정렬의 기본 로직:

진입 차수가 0인 모든 정점을 큐(Queue)에 넣습니다.
큐에서 정점을 하나 꺼내 결과 리스트에 추가합니다.
해당 정점과 연결된 모든 간선을 제거합니다. (즉, 다음 정점들의 진입 차수를 1씩 줄입니다.)
이때 진입 차수가 0이 된 정점이 있다면 다시 큐에 넣습니다.
큐가 빌 때까지 반복합니다.

시간 복잡도 분석

모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 확인합니다.
따라서 시간 복잡도는 O(V + E) 입니다. (V: 정점의 개수, E: 간선의 개수)
정말 빠르죠? 데이터가 많아도 효율적으로 처리할 수 있는 아주 훌륭한 알고리즘입니다.

초보자 폭풍 질문! “재준봇님! 큐 말고 그냥 리스트를 써도 되나요? 아니면 스택을 써도 되나요?”

재준봇의 명쾌한 답변: 오, 좋은 질문입니다! 위상 정렬의 핵심은 ‘진입 차수가 0이 된 것을 즉시 처리하는 것’입니다. 따라서 먼저 들어온 것을 먼저 처리하는 FIFO(First-In-First-Out) 구조인 큐가 가장 적합하고 직관적입니다. 물론 스택을 써도 결과는 나오지만, 보통은 큐를 사용하는 것이 표준입니다. 큐를 사용해야 논리적인 흐름이 가장 깔끔하거든요!

실무주의보 현업에서 위상 정렬은 생각보다 정말 많이 쓰입니다. 예를 들어, 소프트웨어 빌드 시스템(Makefile, Gradle 등)에서 어떤 라이브러리를 먼저 컴파일해야 하는지 결정할 때 사용합니다. 또한 엑셀의 수식 계산 순서를 정할 때도 사용되죠. 하지만 실제 실무에서는 ‘순환 참조(Circular Dependency)’가 발생하는 경우가 빈번합니다. A가 B를 참조하고 B가 A를 참조하는 상황이죠. 이때 위상 정렬 결과의 개수가 전체 정점의 개수보다 적다면 “순환 참조가 발생했다!”라고 판단하여 에러를 띄워줘야 합니다. 이 예외 처리를 빼먹으면 프로그램이 무한 루프에 빠지거나 멈출 수 있으니 꼭 기억하세요!

해결 방안 및 정답 코드 보기 (클릭)

해결 방안 가이드 (알고리즘 설계)

그래프 구성: 인접 리스트를 사용하여 퀘스트 간의 연결 관계를 저장합니다.
진입 차수 배열 생성: 각 퀘스트마다 몇 개의 선행 퀘스트가 있는지 기록하는 배열을 만듭니다.
시작점 찾기: 진입 차수가 0인 퀘스트(선행 조건이 없는 것)를 모두 찾아 큐에 넣습니다.
순서 결정: 큐에서 하나씩 꺼내며 방문 순서를 기록하고, 연결된 다음 퀘스트들의 진입 차수를 1씩 감소시킵니다.
반복: 감소시킨 후 진입 차수가 0이 된 퀘스트가 있다면 큐에 추가합니다.
검증: 최종 결과 리스트의 길이가 전체 퀘스트 수와 같은지 확인하여 사이클 유무를 판별합니다.

파이썬 정답 코드 및 상세 해설

from collections import deque

def solve_quest_order():
    # 1. 데이터 정의
    # n: 퀘스트의 개수, m: 선행 관계의 개수
    n = 5 
    # 선행 관계: (선행 퀘스트, 후행 퀘스트)
    edges = [
        (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)
    ]

    # 2. 그래프 및 진입 차수 초기화
    graph = [[] for _ in range(n + 1)]
    indegree = [0] * (n + 1)

    # 그래프 구축 및 진입 차수 계산
    for pre, nxt in edges:
        graph[pre].append(nxt)  # pre 다음에 nxt를 해야 함
        indegree[nxt] += 1      # nxt의 진입 차수 증가

    # 3. 진입 차수가 0인 노드를 큐에 삽입
    queue = deque()
    for i in range(1, n + 1):
        if indegree[i] == 0:
            queue.append(i)

    result = []

    # 4. 위상 정렬 수행
    while queue:
        now = queue.popleft()
        result.append(now)

        # 현재 노드와 연결된 노드들의 진입 차수에서 1 빼기
        for next_node in graph[now]:
            indegree[next_node] -= 1
            # 새롭게 진입 차수가 0이 된 노드를 큐에 삽입
            if indegree[next_node] == 0:
                queue.append(next_node)

    # 5. 사이클 확인 및 결과 출력
    if len(result) == n:
        print("퀘스트 수행 가능 순서:", result)
    else:
        print("에러: 퀘스트 순환 참조가 발생하여 수행할 수 없습니다!")

# 함수 실행
solve_quest_order()

코드 상세 해설:

from collections import deque: 파이썬의 일반 리스트보다 popleft() 연산이 훨씬 빠른 deque를 사용했습니다. (시간 복잡도 $O(1)$)
graph = [[] for _ in range(n + 1)]: 인덱스를 퀘스트 번호와 맞추기 위해 n+1 크기로 생성했습니다.
indegree[nxt] += 1: 이 부분이 핵심입니다. 화살표를 받는 쪽의 카운트를 올려서 “아직 준비가 안 됐다”는 것을 표시하는 것입니다.
while queue:: 더 이상 수행할 수 있는 퀘스트가 없을 때까지 계속 반복합니다.
if len(result) == n:: 모든 퀘스트가 결과에 들어갔는지 확인합니다. 만약 덜 들어갔다면, 어딘가에서 서로를 기다리는 사이클이 생겨 진입 차수가 0이 되지 못한 녀석들이 있다는 뜻입니다.

한계점 및 실무 개선점

1. 대규모 데이터 처리 시 메모리 문제

현재는 인접 리스트를 사용하고 있어 효율적이지만, 정점의 개수가 수백만 개가 되면 메모리 사용량이 급증합니다. 이때는 데이터를 디스크에 저장하고 필요한 부분만 불러오는 외부 메모리 알고리즘이나, 분산 처리 시스템을 고려해야 합니다.

2. 동적인 관계 변경

실무에서는 퀘스트 관계가 실시간으로 추가되거나 삭제될 수 있습니다. 매번 위상 정렬을 다시 돌리는 것은 낭비이므로, 변경된 부분만 부분적으로 업데이트하는 ‘증분 위상 정렬(Incremental Topological Sort)’ 기법을 적용하는 것이 좋습니다.

3. 우선순위 반영

단순히 “가능한 순서”가 아니라, “더 중요한 퀘스트부터” 하고 싶다면 deque 대신 PriorityQueue를 사용하여 우선순위가 높은 퀘스트를 먼저 처리하도록 개선할 수 있습니다.

<hr>

💬 궁금한 점이 있다면 자유롭게 댓글을 남겨주세요! (AI 비서가 답변해 드립니다 🤖)

Twitter Facebook LinkedIn