13_topological_sort.py

  1"""
  2위상 정렬 (Topological Sort)
  3Topological Sorting
  4
  5방향 비순환 그래프(DAG)에서 정점을 선형 순서로 나열합니다.
  6"""
  7
  8from typing import List, Dict, Set, Optional, Tuple
  9from collections import deque, defaultdict
 10
 11
 12# =============================================================================
 13# 1. Kahn's 알고리즘 (BFS 기반)
 14# =============================================================================
 15
 16def topological_sort_kahn(n: int, edges: List[Tuple[int, int]]) -> List[int]:
 17    """
 18    Kahn's 알고리즘 (진입 차수 기반)
 19    시간복잡도: O(V + E)
 20    공간복잡도: O(V + E)
 21
 22    edges: [(from, to), ...] - from → to 의존 관계
 23    반환: 위상 정렬된 순서, 사이클 있으면 빈 리스트
 24    """
 25    # 그래프 및 진입 차수 구성
 26    graph = defaultdict(list)
 27    in_degree = [0] * n
 28
 29    for u, v in edges:
 30        graph[u].append(v)
 31        in_degree[v] += 1
 32
 33    # 진입 차수 0인 노드로 시작
 34    queue = deque([i for i in range(n) if in_degree[i] == 0])
 35    result = []
 36
 37    while queue:
 38        node = queue.popleft()
 39        result.append(node)
 40
 41        for neighbor in graph[node]:
 42            in_degree[neighbor] -= 1
 43            if in_degree[neighbor] == 0:
 44                queue.append(neighbor)
 45
 46    # 모든 노드 방문 여부로 사이클 확인
 47    return result if len(result) == n else []
 48
 49
 50# =============================================================================
 51# 2. DFS 기반 위상 정렬
 52# =============================================================================
 53
 54def topological_sort_dfs(n: int, edges: List[Tuple[int, int]]) -> List[int]:
 55    """
 56    DFS 기반 위상 정렬
 57    시간복잡도: O(V + E)
 58    공간복잡도: O(V + E)
 59    """
 60    graph = defaultdict(list)
 61    for u, v in edges:
 62        graph[u].append(v)
 63
 64    WHITE, GRAY, BLACK = 0, 1, 2
 65    color = [WHITE] * n
 66    result = []
 67    has_cycle = False
 68
 69    def dfs(node: int) -> None:
 70        nonlocal has_cycle
 71
 72        if has_cycle:
 73            return
 74
 75        color[node] = GRAY  # 방문 중
 76
 77        for neighbor in graph[node]:
 78            if color[neighbor] == GRAY:  # 사이클 발견
 79                has_cycle = True
 80                return
 81            if color[neighbor] == WHITE:
 82                dfs(neighbor)
 83
 84        color[node] = BLACK  # 방문 완료
 85        result.append(node)
 86
 87    for i in range(n):
 88        if color[i] == WHITE:
 89            dfs(i)
 90
 91    return result[::-1] if not has_cycle else []
 92
 93
 94# =============================================================================
 95# 3. 사이클 탐지
 96# =============================================================================
 97
 98def has_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:
 99    """
100    방향 그래프에서 사이클 존재 여부
101    시간복잡도: O(V + E)
102    """
103    graph = defaultdict(list)
104    for u, v in edges:
105        graph[u].append(v)
106
107    WHITE, GRAY, BLACK = 0, 1, 2
108    color = [WHITE] * n
109
110    def dfs(node: int) -> bool:
111        color[node] = GRAY
112
113        for neighbor in graph[node]:
114            if color[neighbor] == GRAY:
115                return True  # 사이클
116            if color[neighbor] == WHITE and dfs(neighbor):
117                return True
118
119        color[node] = BLACK
120        return False
121
122    for i in range(n):
123        if color[i] == WHITE and dfs(i):
124            return True
125
126    return False
127
128
129# =============================================================================
130# 4. 모든 위상 정렬 순서 찾기
131# =============================================================================
132
133def all_topological_sorts(n: int, edges: List[Tuple[int, int]]) -> List[List[int]]:
134    """
135    모든 가능한 위상 정렬 순서 찾기
136    시간복잡도: O(V! * (V + E)) - 최악의 경우
137    """
138    graph = defaultdict(list)
139    in_degree = [0] * n
140
141    for u, v in edges:
142        graph[u].append(v)
143        in_degree[v] += 1
144
145    result = []
146    path = []
147    visited = [False] * n
148
149    def backtrack():
150        # 모든 노드 방문 완료
151        if len(path) == n:
152            result.append(path.copy())
153            return
154
155        for i in range(n):
156            if not visited[i] and in_degree[i] == 0:
157                # 선택
158                visited[i] = True
159                path.append(i)
160                for neighbor in graph[i]:
161                    in_degree[neighbor] -= 1
162
163                backtrack()
164
165                # 복원
166                visited[i] = False
167                path.pop()
168                for neighbor in graph[i]:
169                    in_degree[neighbor] += 1
170
171    backtrack()
172    return result
173
174
175# =============================================================================
176# 5. 실전 문제: 수강 과목 순서 (Course Schedule)
177# =============================================================================
178
179def can_finish(num_courses: int, prerequisites: List[List[int]]) -> bool:
180    """
181    모든 과목 수강 가능 여부 (사이클 없음 = 가능)
182    prerequisites: [course, prereq] - prereq → course
183    """
184    edges = [(prereq, course) for course, prereq in prerequisites]
185    return not has_cycle(num_courses, edges)
186
187
188def find_order(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
189    """
190    과목 수강 순서 반환
191    """
192    edges = [(prereq, course) for course, prereq in prerequisites]
193    return topological_sort_kahn(num_courses, edges)
194
195
196# =============================================================================
197# 6. 실전 문제: 외계인 사전 (Alien Dictionary)
198# =============================================================================
199
200def alien_order(words: List[str]) -> str:
201    """
202    외계인 알파벳 순서 결정
203    단어 목록이 사전순으로 정렬되어 있다고 가정
204    """
205    # 모든 문자 수집
206    chars = set()
207    for word in words:
208        chars.update(word)
209
210    # 그래프 구성
211    graph = defaultdict(set)
212    in_degree = defaultdict(int)
213    for char in chars:
214        in_degree[char] = 0
215
216    for i in range(len(words) - 1):
217        word1, word2 = words[i], words[i + 1]
218
219        # 유효하지 않은 순서 체크
220        if len(word1) > len(word2) and word1.startswith(word2):
221            return ""
222
223        # 첫 번째 다른 문자로 순서 결정
224        for c1, c2 in zip(word1, word2):
225            if c1 != c2:
226                if c2 not in graph[c1]:
227                    graph[c1].add(c2)
228                    in_degree[c2] += 1
229                break
230
231    # 위상 정렬
232    queue = deque([c for c in chars if in_degree[c] == 0])
233    result = []
234
235    while queue:
236        char = queue.popleft()
237        result.append(char)
238
239        for neighbor in graph[char]:
240            in_degree[neighbor] -= 1
241            if in_degree[neighbor] == 0:
242                queue.append(neighbor)
243
244    return ''.join(result) if len(result) == len(chars) else ""
245
246
247# =============================================================================
248# 7. 실전 문제: 작업 병렬 실행 (Parallel Courses)
249# =============================================================================
250
251def minimum_semesters(n: int, relations: List[List[int]]) -> int:
252    """
253    모든 과목을 수강하는데 필요한 최소 학기 수
254    병렬 수강 가능, relations: [prev, next]
255    """
256    graph = defaultdict(list)
257    in_degree = [0] * (n + 1)
258
259    for prev_course, next_course in relations:
260        graph[prev_course].append(next_course)
261        in_degree[next_course] += 1
262
263    # 진입 차수 0인 노드로 시작 (1-indexed)
264    queue = deque([i for i in range(1, n + 1) if in_degree[i] == 0])
265    semesters = 0
266    completed = 0
267
268    while queue:
269        semesters += 1
270        next_queue = deque()
271
272        while queue:
273            course = queue.popleft()
274            completed += 1
275
276            for next_course in graph[course]:
277                in_degree[next_course] -= 1
278                if in_degree[next_course] == 0:
279                    next_queue.append(next_course)
280
281        queue = next_queue
282
283    return semesters if completed == n else -1
284
285
286# =============================================================================
287# 8. 실전 문제: 최장 경로 (DAG)
288# =============================================================================
289
290def longest_path_dag(n: int, edges: List[Tuple[int, int, int]]) -> List[int]:
291    """
292    DAG에서 각 노드까지의 최장 경로 (가중치 포함)
293    edges: [(from, to, weight), ...]
294    """
295    graph = defaultdict(list)
296    in_degree = [0] * n
297
298    for u, v, w in edges:
299        graph[u].append((v, w))
300        in_degree[v] += 1
301
302    # 위상 정렬
303    topo_order = []
304    queue = deque([i for i in range(n) if in_degree[i] == 0])
305
306    while queue:
307        node = queue.popleft()
308        topo_order.append(node)
309        for neighbor, _ in graph[node]:
310            in_degree[neighbor] -= 1
311            if in_degree[neighbor] == 0:
312                queue.append(neighbor)
313
314    # 최장 경로 계산
315    dist = [0] * n
316
317    for node in topo_order:
318        for neighbor, weight in graph[node]:
319            dist[neighbor] = max(dist[neighbor], dist[node] + weight)
320
321    return dist
322
323
324# =============================================================================
325# 9. 실전 문제: 빌드 순서 결정
326# =============================================================================
327
328def build_order(projects: List[str], dependencies: List[Tuple[str, str]]) -> List[str]:
329    """
330    빌드 순서 결정
331    dependencies: [(proj, depends_on), ...] - proj가 depends_on에 의존
332    """
333    # 프로젝트 인덱스 매핑
334    proj_to_idx = {p: i for i, p in enumerate(projects)}
335    n = len(projects)
336
337    # 간선 변환 (depends_on → proj)
338    edges = [(proj_to_idx[dep], proj_to_idx[proj]) for proj, dep in dependencies]
339
340    # 위상 정렬
341    order = topological_sort_kahn(n, edges)
342
343    if not order:
344        return []  # 사이클 존재
345
346    return [projects[i] for i in order]
347
348
349# =============================================================================
350# 테스트
351# =============================================================================
352
353def main():
354    print("=" * 60)
355    print("위상 정렬 (Topological Sort) 예제")
356    print("=" * 60)
357
358    # 1. Kahn's 알고리즘
359    print("\n[1] Kahn's 알고리즘 (BFS)")
360    n = 6
361    edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
362    result = topological_sort_kahn(n, edges)
363    print(f"    노드: 0-5, 간선: {edges}")
364    print(f"    위상 정렬: {result}")
365
366    # 2. DFS 기반
367    print("\n[2] DFS 기반 위상 정렬")
368    result = topological_sort_dfs(n, edges)
369    print(f"    위상 정렬: {result}")
370
371    # 3. 사이클 탐지
372    print("\n[3] 사이클 탐지")
373    cyclic_edges = [(0, 1), (1, 2), (2, 0)]
374    acyclic_edges = [(0, 1), (1, 2), (0, 2)]
375    print(f"    {cyclic_edges}: 사이클 {has_cycle(3, cyclic_edges)}")
376    print(f"    {acyclic_edges}: 사이클 {has_cycle(3, acyclic_edges)}")
377
378    # 4. 모든 위상 정렬
379    print("\n[4] 모든 위상 정렬 순서")
380    n = 4
381    edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
382    all_orders = all_topological_sorts(n, edges)
383    print(f"    노드: 0-3, 간선: {edges}")
384    print(f"    모든 순서: {all_orders}")
385
386    # 5. 과목 수강 순서
387    print("\n[5] 과목 수강 순서")
388    num_courses = 4
389    prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
390    can = can_finish(num_courses, prerequisites)
391    order = find_order(num_courses, prerequisites)
392    print(f"    과목 수: {num_courses}, 선수: {prerequisites}")
393    print(f"    수강 가능: {can}")
394    print(f"    순서: {order}")
395
396    # 6. 외계인 사전
397    print("\n[6] 외계인 사전")
398    words = ["wrt", "wrf", "er", "ett", "rftt"]
399    order = alien_order(words)
400    print(f"    단어: {words}")
401    print(f"    알파벳 순서: {order}")
402
403    # 7. 최소 학기 수
404    print("\n[7] 최소 학기 수")
405    n = 3
406    relations = [[1, 3], [2, 3]]
407    semesters = minimum_semesters(n, relations)
408    print(f"    과목: {n}, 관계: {relations}")
409    print(f"    최소 학기: {semesters}")
410
411    # 8. DAG 최장 경로
412    print("\n[8] DAG 최장 경로")
413    n = 4
414    edges = [(0, 1, 3), (0, 2, 2), (1, 3, 4), (2, 3, 1)]
415    dist = longest_path_dag(n, edges)
416    print(f"    간선: {edges}")
417    print(f"    각 노드까지 최장 거리: {dist}")
418
419    # 9. 빌드 순서
420    print("\n[9] 빌드 순서")
421    projects = ['a', 'b', 'c', 'd', 'e', 'f']
422    dependencies = [('d', 'a'), ('b', 'f'), ('d', 'b'), ('a', 'f'), ('c', 'd')]
423    order = build_order(projects, dependencies)
424    print(f"    프로젝트: {projects}")
425    print(f"    의존성: {dependencies}")
426    print(f"    빌드 순서: {order}")
427
428    print("\n" + "=" * 60)
429
430
431if __name__ == "__main__":
432    main()