DFS 후위 순서 위상 정렬
DFS를 실행해 각 노드의 이웃을 모두 탐색한 후 해당 노드를 스택에 넣고, 스택에서 꺼내 유효한 위상 순서를 만듭니다.
DFS 후위 순서 위상 정렬은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
DFS 기반 위상 정렬 아이디어
두 번째 고전적인 위상 정렬 알고리즘은 후위 순서 처리를 사용하는 DFS입니다. 노드의 모든 이웃과 그 자손을 완전히 탐색한 후 해당 노드를 스택에 넣습니다. 모든 노드를 처리하면 스택에서 pop하여 위상 순서를 읽습니다. 모든 의존 항목을 처리한 후 스택에 들어간 노드는 순서에서 앞에 와야 하므로, 후위 순서를 뒤집은 것이 위상 정렬입니다.
후위 순서의 직관
A 과목을 수강하려면 B 과목이 필요하다고 하겠습니다. DFS가 A를 방문하면 먼저 B로 재귀 호출합니다. B에는 선수 과목이 없으므로 먼저 처리가 끝나고 스택에 먼저 들어갑니다. 그런 다음 A의 처리가 끝나고 스택에 들어갑니다. 스택에서 pop하면 출력 결과에서 A가 B보다 앞에 오지만, 마지막에 순서를 뒤집으므로 B가 A보다 앞에 옵니다. 즉, B를 먼저 수강한 다음 A를 수강하게 됩니다. 후위 순서는 의존 항목을 의존하는 항목보다 먼저 스택에 넣으므로, 뒤집은 스택은 유효한 위상 순서가 됩니다.
사이클 탐지를 위한 세 색상 DFS
방문 상태를 세 가지로 구분합니다. WHITE (0)는 방문하지 않음, GREY (1)는 현재 처리 중임(DFS 호출 스택에 있음), BLACK (2)는 처리가 완전히 끝남을 의미합니다. 후향 간선, 즉 GREY 노드로 향하는 간선은 사이클이 있음을 나타냅니다. BLACK 노드로 향하는 간선은 이미 완전히 탐색했으므로 안전합니다. 이 세 색상 방식은 방향 그래프의 모든 사이클을 정확하게 탐지합니다.
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)전체 DFS 위상 정렬 구현
노드에 색상을 지정하고, 후위 순서로 스택에 넣으며, 사이클이 발견되면 거짓을 반환하는 재귀 DFS를 사용합니다. 모든 노드를 방문한 후 스택을 뒤집으면 위상 순서를 얻을 수 있습니다.
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))스택 오버플로를 피하는 반복형 DFS
파이썬의 재귀 한도(기본값 1000)는 큰 그래프에서 문제가 될 수 있습니다. 명시적인 스택을 사용하는 반복형 DFS로 이를 피할 수 있습니다. 핵심은 처음에 (node, False)를 넣는 것입니다. False 상태로 꺼냈다면 (node, True)를 넣어 '탐색한 후 여기로 돌아오겠습니다'라는 뜻을 표시하고, 방문하지 않은 모든 이웃을 False 상태로 넣습니다. True 상태로 꺼냈을 때는 해당 노드에 BLACK을 지정하고 결과 스택에 넣습니다.
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]DFS와 칸 알고리즘 비교
두 알고리즘 모두 O(V + E) 시간에 실행됩니다. 주요 차이점은 다음과 같습니다. 칸 알고리즘(BFS)은 의존성이 가장 이른 노드부터 자연스럽게 생성하며, 사이클 탐지도 더 간단하게 길이 확인으로 처리할 수 있습니다. DFS 후위 순서는 재귀적으로 동작하고 후향 간선을 명시적으로 탐지합니다. 순서를 뒤집지 않고 정방향 결과를 얻고 싶다면 칸 알고리즘을 선호합니다. SCC 탐지처럼 다른 목적으로 전체 후위 순서가 필요하다면 DFS를 선호합니다. 면접에서는 두 방법 모두 사용할 수 있습니다.
트리와 DAG에서의 후위 순서
트리에서는 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순서로 후위 순회를 합니다. DAG에서는 후위 DFS가 어떤 노드 자체를 처리하기 전에 해당 노드의 모든 의존 항목을 방문합니다. 이는 여러 선행 노드와 임의의 그래프 구조로 일반화한 동일한 개념입니다. DFS 트리의 루트인 시작 노드는 자손 중 가장 나중에 스택에 들어가므로, 뒤집은 스택에서는 가장 앞에 나타납니다. 이는 선행 노드가 없는 노드에 대한 올바른 위상 순서상의 위치입니다.
외계인 사전 (LeetCode 269)
외계인 사전: 외계 언어로 정렬된 단어 목록이 주어졌을 때 문자 순서를 알아내는 문제입니다. 인접한 단어를 문자별로 비교하여 처음으로 다른 부분을 찾으면 c1 → c2라는 간선을 얻습니다. 이는 c1이 c2보다 앞선다는 뜻입니다. 이러한 간선을 모두 모은 다음 위상 정렬을 수행하여 외계 문자의 순서를 만듭니다. 사이클이 있으면 순서는 유효하지 않습니다.
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'제약 조건이 있는 위상 정렬
일부 문제는 원래 목록에 있는 원소의 상대적 순서를 유지하는 것처럼 추가 조건을 만족하는 위상 정렬을 요구합니다. 칸 알고리즘을 사용자 정의 우선순위 큐 또는 사전 정렬과 결합할 수 있습니다. 각 단계에서 큐의 원소를 안정적으로 정렬하여 원래의 상대적 순서를 유지합니다. 이러한 제약이 있는 변형 문제는 알고리즘의 유연성에 대한 더 깊은 이해를 평가합니다.
위상 정렬 문제 알아보기
면접 문제에서 위상 정렬을 암시하는 표현은 다음과 같습니다. '의존성이 주어졌을 때', '선수 과목', '작업 순서', '빌드 순서', '모든 작업을 완료할 수 있는가?', '유효한 순서 찾기'. 어떤 항목은 다른 항목보다 먼저 와야 하는 순서를 다루는 문제라면, 방향 그래프를 만들고 칸 알고리즘 또는 DFS 위상 정렬을 적용합니다. 같은 문제에서 사이클 탐지가 추가 요구 사항으로 등장하는 경우가 많습니다.
DFS와 칸 알고리즘의 출력 비교
DFS와 칸 알고리즘은 같은 그래프에 대해 서로 다른 유효한 위상 순서를 만들 수 있습니다. 둘 다 올바릅니다. DAG에는 유효한 위상 순서가 여러 개 있을 수 있기 때문입니다. 올바른지 확인하려면 그래프의 모든 간선 u → v에 대해 출력 순서에서 u가 v보다 앞에 나타나는지 확인합니다. 사전순으로 가장 작은 순서처럼 특정 순서가 필요한 면접 문제라면 최소 힙을 사용하는 칸 알고리즘을 이용하십시오. DFS 후위 순서는 사전순 최솟값을 자연스럽게 만들지 못합니다.
빠른 확인
이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 테스트하십시오.
단원 복습
이 단원에서는 다음을 배웠습니다. DFS 후위 순서 위상 정렬은 모든 의존 항목을 탐색한 후 노드를 스택에 넣습니다. 세 색상 표시(WHITE/GREY/BLACK)는 GREY 노드로 향하는 후향 간선을 통해 사이클을 탐지합니다. 또한 후위 순서 스택을 뒤집으면 유효한 위상 순서를 얻을 수 있습니다. 다음에는 위상 정렬을 과목 일정 I 및 II 문제에 직접 적용합니다.
자주 묻는 질문
“DFS 후위 순서 위상 정렬” 강의는 무료인가요?
네 — “DFS 후위 순서 위상 정렬” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“DFS 후위 순서 위상 정렬”에서 뭘 배우나요?
DFS를 실행해 각 노드의 이웃을 모두 탐색한 후 해당 노드를 스택에 넣고, 스택에서 꺼내 유효한 위상 순서를 만듭니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“DFS 후위 순서 위상 정렬” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 칸 알고리즘: BFS 위상 정렬
- DFS 후위 순서 위상 정렬
- 과목 일정 I과 II
- 코사라주를 사용한 강한 연결 요소