Coding Interview Prep · 강의

칸 알고리즘: BFS 위상 정렬

Q: “칸 알고리즘: BFS 위상 정렬” 강의는 무료인가요?

네 — “칸 알고리즘: BFS 위상 정렬” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

Q: “칸 알고리즘: BFS 위상 정렬” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

모든 노드의 진입 차수를 계산하고 진입 차수가 0인 노드를 큐에 넣은 뒤 큐를 처리해 위상 순서를 만들면서 사이클을 탐지합니다.

칸 알고리즘: BFS 위상 정렬은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

위상 정렬이란 무엇인가요

위상 정렬은 유향 비순환 그래프(DAG)의 노드를 정렬하는 방법으로, 모든 방향 간선 u → v에 대해 정렬 순서에서 u가 v보다 앞에 오도록 합니다. 이는 의존성이 있는 작업의 유효한 실행 순서를 나타내며, 빌드 시스템, 강의 일정 관리, 패키지 관리 등에 활용됩니다. 유효한 위상 순서를 가질 수 있는 것은 DAG뿐이며, 순환이 있으면 위상 순서를 만들 수 없습니다.

칸 알고리즘: 핵심 아이디어

칸 알고리즘은 BFS 기반의 위상 정렬 방법입니다. 핵심은 진입 차수가 0인 노드(선행 조건이 없는 노드)를 순서의 첫 부분에 배치할 수 있다는 것입니다. 노드를 배치한 후에는 해당 노드를 제거하고 이웃 노드의 진입 차수를 감소시킵니다. 새롭게 진입 차수가 0이 된 노드를 사용할 수 있게 됩니다. 모든 노드를 배치하거나 순환이 발견될 때까지 반복합니다. 순환이 있으면 진입 차수가 0이 되지 않은 노드가 남습니다.

진입 차수 계산

먼저 인접 리스트를 만들고 각 노드의 진입 차수(들어오는 간선의 수)를 계산합니다. 진입 차수가 0인 노드는 의존성이 없으므로 시작점이 됩니다. 간선이 [(0,1),(0,2),(1,3),(2,3)]인 그래프의 진입 차수는 다음과 같습니다. 0→0, 1→1, 2→1, 3→2. 진입 차수 0으로 시작하는 노드는 0뿐입니다.

from collections import deque, defaultdict

def compute_in_degree(n, edges):
    in_degree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    return graph, in_degree

graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind)  # [0, 1, 1, 2]

칸 알고리즘 구현

진입 차수가 0인 모든 노드를 큐에 넣습니다. 각 노드를 처리할 때 결과에 추가한 다음, 모든 이웃 노드의 진입 차수를 감소시키고 진입 차수가 0이 되면 큐에 넣습니다. 결과 목록의 노드 수가 그래프의 노드 수보다 적다면 순환이 존재하는 것입니다. 일부 노드는 큐에서 꺼낼 수 없었기 때문입니다.

from collections import deque, defaultdict

def kahn_topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    if len(order) == n:
        return order   # valid topological sort
    return []          # cycle detected

print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))

칸 알고리즘을 통한 순환 탐지

칸 알고리즘은 추가 비용 없이 순환을 탐지할 수 있습니다. len(order) < n이면 진입 차수가 0이 되지 않아 큐에 추가되지 않은 노드가 있다는 뜻이며, 이 노드들은 순환의 일부입니다. 색상으로 표시하는 방문 배열을 유지하는 것보다 더 간단한 방법입니다. 순환이 존재한다는 것을 나타내기 위해 빈 목록을 반환합니다.

# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result)  # [] (cycle detected)

# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result)  # [0, 1, 2]

시간 및 공간 복잡도

칸 알고리즘은 각 노드를 한 번씩 처리하고(한 번씩 큐에서 꺼냅니다), 각 간선도 한 번씩 처리합니다(한 번씩 진입 차수를 감소시킵니다). 시간 복잡도는 O(V + E)입니다. 공간 복잡도는 인접 리스트와 진입 차수 배열에 O(V + E), 큐에 O(V)입니다. 이는 최적입니다. 유효한 순서를 만들려면 최소한 모든 노드와 간선을 읽어야 하기 때문입니다.

사전순으로 가장 앞선 위상 순서

큐 대신 최소 힙을 사용하는 칸 알고리즘은 사전순으로 가장 앞선 위상 순서를 생성합니다. deque를 heapq로 바꾸고, (node)를 삽입한 다음 사용할 수 있는 노드 중 가장 작은 노드를 항상 먼저 처리합니다. 이렇게 하면 가능한 모든 위상 정렬 중 사전순으로 가장 앞선 유효한 순서가 보장됩니다.

import heapq
from collections import defaultdict

def kahn_lex_order(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    heap = [i for i in range(n) if in_degree[i] == 0]
    heapq.heapify(heap)
    order = []
    
    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, nxt)
    
    return order if len(order) == n else []

print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))

응용: 수강 일정 I

수강 일정(LeetCode 207) 문제에서는 n개의 강의와 선수 과목이 주어질 때 모든 강의를 수강할 수 있는지 묻습니다. 선수 과목 관계를 방향 간선으로 모델링하고 유효한 위상 정렬이 존재하는지, 즉 순환이 없는지 확인합니다. 칸 알고리즘이 길이 n인 순서를 생성하면 참을 반환하고, 순환이 발견되면 거짓을 반환합니다.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:   # b must be taken before a
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))       # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)

응용: 수강 일정 II

수강 일정 II(LeetCode 210)에서는 강의를 수강해야 하는 실제 순서를 반환합니다. 위 문제와 동일하지만 불리언 값 대신 order 목록을 반환합니다. 순환이 존재하면 빈 목록을 반환합니다. 칸 알고리즘의 결과를 답으로 직접 사용할 수 있습니다.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

병렬 작업 일정 관리

더 발전된 활용으로, 의존성이 없는 작업을 병렬로 실행할 수 있을 때 필요한 최소 ‘라운드’ 수를 구할 수 있습니다. 칸 알고리즘을 BFS의 레벨 순서와 비슷하게 레벨별로 처리합니다. 진입 차수가 0인 모든 노드를 큐에 넣고, 현재 큐 전체를 하나의 라운드로 처리한 다음, 새롭게 실행할 수 있게 된 노드를 다음 라운드로 큐에 넣습니다. 라운드 수를 셉니다.

from collections import deque, defaultdict

def min_rounds(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    rounds = 0
    while queue:
        rounds += 1
        for _ in range(len(queue)):  # process current level
            node = queue.popleft()
            for nxt in graph[node]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
    return rounds

print(min_rounds(4, [(0,2),(1,2),(2,3)]))  # 3

DAG에서의 위상 정렬과 DP

위상 정렬을 사용하면 DAG에서 동적 프로그래밍을 수행할 수 있습니다. 노드를 위상 순서대로 처리하면 각 노드의 동적 프로그래밍 값을 계산할 때 모든 선행 노드의 값이 이미 확정되어 있습니다. 이는 위상 정렬과 DP를 결합하여 DAG의 최장 경로, 모든 노드에 도달하는 최소 비용, 의존성 연결에서 얻는 최대 이익과 같은 문제를 해결합니다. 이 순서 덕분에 모든 의존성을 처리한 후 각 노드의 DP 값을 정확히 한 번 계산할 수 있습니다.

from collections import deque, defaultdict

def longest_path_dag(V, edges):
    graph = defaultdict(list)
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    dp = [0] * V
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
            in_degree[v] -= 1
            if in_degree[v] == 0: queue.append(v)
    return max(dp)

print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)]))  # 7

빠른 확인

이 수업에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.

수업 요약

이 수업에서는 다음을 배웠습니다. 칸 알고리즘은 진입 차수가 0인 노드를 BFS로 반복해서 제거하며 위상 정렬을 계산합니다. 순환 탐지는 추가 비용 없이 수행되며, 결과 순서의 길이가 n보다 작으면 순환이 존재합니다. 또한 큐를 최소 힙으로 바꾸면 사전순으로 가장 앞선 위상 순서를 얻을 수 있습니다. 다음에는 칸 알고리즘의 대안으로 DFS 기반 후위 순서 위상 정렬을 살펴보겠습니다.

자주 묻는 질문