DFS 기반 Topological Sort 위상 정렬 구현

1) DFS 기반 위상 정렬

# 주어진 방향성 있는 비순환 그래프(DAG)에서
# 올바른 위상 정렬 순서를 반환하는 함수
def topologicalSort(edges, n):
    # 1. 인접 리스트(adj)를 만들어서 그래프 구성
    adj = {}
    for i in range(1, n + 1):
        adj[i] = []  # 각 노드를 key로 하여 빈 리스트 초기화

    # 주어진 간선을 이용해 방향 그래프 구성 (src → dst)
    for src, dst in edges:
        adj[src].append(dst)

    # 2. 위상 정렬 결과를 담을 리스트
    topSort = []

    # 방문한 노드를 기록할 집합
    visit = set()

    # 3. 모든 노드에 대해 DFS 수행 (그래프가 연결되어 있지 않을 수도 있으므로)
    for i in range(1, n + 1):
        dfs(i, adj, visit, topSort)

    # DFS는 후위 순회로 topSort에 쌓으므로, 결과를 뒤집어야 올바른 순서가 됨
    topSort.reverse()
    return topSort

# 깊이 우선 탐색 (DFS) 함수
def dfs(src, adj, visit, topSort):
    # 이미 방문한 노드면 중복 탐색 방지
    if src in visit:
        return

    # 현재 노드 방문 표시
    visit.add(src)

    # 현재 노드에서 연결된 이웃 노드들에 대해 재귀 DFS
    for neighbor in adj[src]:
        dfs(neighbor, adj, visit, topSort)

    # 모든 이웃 노드 탐색이 끝난 후 → 현재 노드를 결과 리스트에 추가
    # 즉, 후위 순회(post-order): 자식들을 다 방문한 후 자신을 추가
    topSort.append(src)

✅ 핵심 포인트 요약

포인트	설명
후위 순회	자식 노드를 먼저 모두 방문한 후에 자신을 결과에 추가
visit 집합	DFS 중복 탐색 방지
reverse()	DFS 결과는 역순으로 쌓이므로 마지막에 뒤집어야 정답 순서
DAG	위상 정렬은 반드시 사이클 없는 방향 그래프에서만 가능

2) DFS 기반 위상 정렬 + 사이클 감지 기능이 포함된 코드

class Solution:
    def topologicalSort(self, n: int, edges: List[List[int]]) -> List[int]:
        from collections import defaultdict

        # 1. 방향 그래프를 인접 리스트로 구성
        adj = defaultdict(list)
        for src, dst in edges:
            adj[src].append(dst)  # src → dst (단방향 간선)

        # 2. 위상 정렬 결과 저장 리스트
        topSort = []

        # 방문한 노드를 저장하는 집합
        visited = set()  # DFS가 완전히 끝난 노드
        visiting = set() # 현재 DFS 경로상에 있는 노드 (사이클 감지용)

        # 3. DFS 함수 정의
        def dfs(src: int) -> bool:
            # 이미 처리된 노드는 다시 처리할 필요 없음
            if src in visited:
                return True

            # 현재 DFS 경로에서 다시 이 노드를 만났다면 → 사이클 존재
            if src in visiting:
                return False

            # 현재 노드를 방문 경로에 추가
            visiting.add(src)

            # 모든 이웃 노드에 대해 DFS 수행
            for neighbor in adj[src]:
                if not dfs(neighbor):  # 사이클이 감지되면 false 리턴
                    return False

            # 이 노드의 모든 이웃 탐색이 끝남 → 방문 경로에서 제거
            visiting.remove(src)

            # 이 노드는 완전히 처리됨 → visited로 이동
            visited.add(src)

            # 후위 순회: 이 노드를 결과 리스트에 추가
            topSort.append(src)

            return True  # 이 노드로부터의 경로에는 사이클 없음

        # 4. 모든 노드에 대해 DFS 수행
        for i in range(n):
            if not dfs(i):
                return []  # 사이클이 감지되면 위상 정렬 불가능 → 빈 리스트 반환

        # 5. 후위 순회 결과는 역순이므로 뒤집어서 반환
        topSort.reverse()
        return topSort

class Solution:
    def topologicalSort(self, n: int, edges: List[List[int]]) -> List[int]:
        # edges = [src, dst] 순서, adj[선수과목] = [이후 수강 가능한 과목, ...]
        # return valid ordering
        adj = {}
        for i in range(n):
            adj[i] = []
        for src, dst in edges:
            adj[src].append(dst)

        topSort = []
        visit = set() # 방문 완료한 노드
        visiting = set() # 현재 방문중인 노드, 사이클 감지용

        def dfsCycleCheck(src):
            if src in visit: # 이미 방문완료된 노드면
                return True  # 이 경로에는 싸이클 없음
            
            if src in visiting: # 현재 방문중인데, dfs 경로에서 또 만났으니, 싸이클임
                return False # 사이클 감지

            visiting.add(src) # 방문중: 현재 노드를 방문 경로에 추가

            for dst in adj[src]:
                if not dfsCycleCheck(dst): # dst 에 사이클이 감지 되면
                    return False # 싸이클 감지

            visiting.remove(src) # 방문중 해제: 현재 노드를 방문 경로에 삭제
            visit.add(src) # 현재 노드를 방문 완료로 추가

            topSort.append(src) # 후위 순회(post-order) 현재 노드를 결과리스트에 추가
            return True # 이 경로에는 싸이클 없음

        # 모든 노드에 대해서 사이클 확인 체크
        for i in range(n):
            if not dfsCycleCheck(i): # 하나라도 싸이클 감지되면
                return []

        # 후위순회(post-order) 결과는 역순이므로 뒤집어서 반환
        return topSort[::-1]

✅ 핵심 요약

요소	설명
visited	DFS가 완전히 끝난 노드 (결과에 포함됨)
visiting	현재 DFS 호출 스택에 있는 노드 (사이클 감지용)
if src in visiting	현재 경로에 있는 노드를 또 만남 → 사이클 존재
topSort.reverse()	후위 순회 방식이라 뒤집어야 위상 정렬 순서가 됨