위상정렬: Graphs (싸이클탐지): 210. Course Schedule II★

210. Course Schedule II

 

Hint 1

 

This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

 

 

Hint 2

 

Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

 

Hint 3

 

Topological sort could also be done via BFS.

 

힌트 1

이 문제는 유향 그래프에서 위상 순서를 찾는 것과 같습니다. 사이클이 있는 경우 위상 순서가 존재하지 않으므로 모든 과정을 수강하는 것은 불가능합니다.

힌트 2

DFS를 통한 위상 정렬 - Coursera의 위상 정렬의 기본 개념을 설명하는 훌륭한 비디오 튜토리얼(21분)

힌트 3

위상 정렬은 BFS를 통해서도 수행할 수 있습니다.

 

문제 요약

이 문제는 위상 정렬(Topological Sort) 알고리즘을 사용하여 해결해야 합니다. 위상 정렬은 그래프의 정점들을 "순서대로 정렬"하는 알고리즘으로, 방향성 있는 비순환 그래프(DAG, Directed Acyclic Graph)에서 주로 사용됩니다.

---

• numCourses: 수강해야 할 총 과목 수. 과목은 0부터 numCourses - 1까지 번호가 매겨져 있음.
• prerequisites: 각 쌍 [a, b]는 과목 a를 듣기 위해 먼저 b를 들어야 함을 의미.
• 목표: 모든 과목을 완료할 수 있는 순서를 반환하고, 불가능하면 빈 배열 []을 반환.

해결 접근법

1. 그래프 모델링:
   • 각 과목을 노드로 보고, 선수 과목 관계를 유향 간선으로 표현합니다.
   • prerequisites를 기반으로 인접 리스트를 생성합니다.
2. 진입 차수 계산:
   • 각 노드(과목)에 들어오는 간선의 개수(진입 차수, in-degree)를 계산합니다.
   • 진입 차수가 0인 노드는 선수 과목이 없는 과목이므로 바로 수강할 수 있습니다.
3. 위상 정렬:
   • BFS 방식으로 진입 차수가 0인 노드를 큐에 넣고 하나씩 꺼내면서 순서를 기록합니다.
   • 노드에 연결된 다음 노드들의 진입 차수를 감소시키고, 진입 차수가 0이 되면 큐에 추가합니다.
4. 결과 검증:
   • 모든 노드를 방문했는지 확인합니다. 만약 모든 노드를 방문하지 못했다면 순환이 존재하므로 빈 배열을 반환합니다.

 

코드 (BFS 기반 위상 정렬)

from collections import defaultdict, deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 그래프 초기화 (인접 리스트) 및 진입 차수 초기화
        graph = defaultdict(list)
        in_degree = [0] * numCourses
        
        # 그래프 생성 및 진입 차수 계산
        for course, pre in prerequisites:
            graph[pre].append(course)  # pre -> course
            in_degree[course] += 1     # course의 진입 차수 +1
        
        # 진입 차수가 0인 노드(과목)를 큐에 추가
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        order = []  # 수강 순서 저장
        
        # 위상 정렬 수행
        while queue:
            course = queue.popleft()
            order.append(course)  # 순서에 추가
            
            # 해당 노드와 연결된 노드들의 진입 차수 감소
            for next_course in graph[course]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    queue.append(next_course)
        
        # 모든 과목을 완료할 수 있는지 확인
        return order if len(order) == numCourses else []

 

코드 설명

1. 그래프 생성
   • graph에 선수 과목 관계를 저장합니다.
   • in_degree 배열에 각 노드의 진입 차수를 저장합니다.
2. 큐 초기화
   • 진입 차수가 0인 노드를 찾아 큐에 넣습니다.
3. 위상 정렬
   • 큐에서 노드를 꺼내고, 해당 노드와 연결된 노드들의 진입 차수를 줄입니다.
   • 진입 차수가 0이 되면 큐에 추가합니다.
   • 이 과정을 반복하면서 순서를 기록합니다.
4. 결과 검증
   • order에 기록된 노드의 개수가 numCourses와 같으면 순서를 반환하고, 아니면 빈 배열을 반환합니다.

 

https://youtu.be/Akt3glAwyfY?si=FskxT3P6hLYgwiu4

 

위상 정렬을 DFS를 사용하여 구현한 것입니다.

위상 정렬은 **유향 비순환 그래프(DAG)**에서 정점의 순서를 정렬하는 방법입니다.

---

주요 개념

1. 그래프 표현:
   • 과목을 노드로 보고, 선수 과목 관계를 유향 간선으로 나타냅니다.
   • 이를 **인접 리스트(adjacency list)**를 사용해 prereq라는 딕셔너리에 저장합니다.
2. DFS를 이용한 탐색:
   • 각 노드는 3가지 상태 중 하나입니다:
     • unvisited: 아직 방문하지 않은 노드.
     • visiting: 현재 탐색 중인 노드 (순환을 감지할 수 있음).
     • visited: 이미 탐색이 완료된 노드.
3. 순환 감지:
   • DFS 도중 이미 visiting 상태인 노드를 다시 방문하면 순환이 존재하므로 False를 반환합니다.
4. 결과 저장:
   • DFS 탐색이 완료된 노드는 output 리스트에 저장되며, 최종적으로 모든 노드를 탐색하면 과목 순서가 반환됩니다.

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 위상 정렬(Topological Sort) via DFS using hashset
        # 선수 과목 관계를 저장할 인접 리스트 초기화
        prereq = {c: [] for c in range(numCourses)}

        # prerequisites를 기반으로 그래프(인접 리스트) 생성
        for crs, pre in prerequisites:
            prereq[crs].append(pre)

        # 각 노드(과목)의 상태를 나타내기 위한 집합
        output = []  # 위상 정렬 결과 저장
        visit = set()  # 이미 탐색이 완료된 노드
        cycle = set()  # 탐색 중인 노드 (순환 감지용)

        # DFS 함수 정의
        def dfs(crs):
            # 순환 감지: 현재 노드가 탐색 중(cycle)에 다시 방문된 경우
            if crs in cycle:
                return False  # 순환이 있으므로 실패
            
            # 이미 방문 완료된 노드라면 더 탐색할 필요 없음
            if crs in visit:
                return True  # 탐색 성공
            
            # 현재 노드를 탐색 중 상태로 추가
            cycle.add(crs)
            # 현재 노드의 모든 선수 과목에 대해 DFS 탐색
            for pre in prereq[crs]:
                if dfs(pre) == False:  # 순환이 감지되면 실패
                    return False
            
            # 탐색이 끝났으므로 현재 노드를 탐색 중 상태에서 제거
            cycle.remove(crs)
            # 현재 노드를 방문 완료 상태로 표시
            visit.add(crs)
            # 결과 리스트에 현재 노드를 추가 (위상 정렬 순서)
            output.append(crs)
            return True  # 탐색 성공

        # 모든 과목에 대해 DFS 탐색 시작
        for c in range(numCourses):
            if dfs(c) == False:  # 순환이 감지되면 빈 리스트 반환
                return []

        # 결과 리스트를 반환 (과목 순서)
        return output

 

좀더 최적화

 

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 선수 과목 리스트를 저장할 딕셔너리를 초기화합니다.
        # Initialize a dictionary to store prerequisite lists for each course.
        preReq = {i: [] for i in range(numCourses)}

        # prerequisites 리스트를 기반으로 각 과목의 선수 과목을 매핑합니다.
        # Populate the prerequisite dictionary based on the prerequisites list.
        for crs, pre in prerequisites:
            preReq[crs].append(pre)

        # 순환 여부를 감지하기 위한 집합 (DFS 경로 추적용).
        # A set to detect cycles (used to track nodes in the current DFS path).
        cycle = set()

        # 결과를 저장할 리스트 (위상 정렬 순서를 담음).
        # A list to store the final result (topological order).
        res = []

        # DFS 함수를 정의합니다.
        # Define the DFS function.
        def dfs(crs):
            # 현재 노드가 순환 집합에 있다면, 싸이클이 발생한 것입니다.
            # If the current node is in the cycle set, a cycle has been detected.
            if crs in cycle:
                return False  # 싸이클 감지 시 False 반환
                # Return False when a cycle is detected.

            # 현재 노드가 이미 결과 리스트에 있다면, 이미 탐색이 완료된 것입니다.
            # If the current node is already in the result list, it is already processed.
            if crs in res:
                return True  # 이미 탐색된 경우 True 반환
                # Return True as it has been successfully processed.

            # 현재 노드를 순환 집합에 추가하여 방문 표시를 합니다.
            # Add the current node to the cycle set to mark it as visited in the current DFS path.
            cycle.add(crs)

            # 현재 과목의 선수 과목들을 재귀적으로 탐색합니다.
            # Recursively visit all prerequisites of the current course.
            for pre in preReq[crs]:
                if not dfs(pre):  # 선수 과목을 탐색 중 싸이클 발견 시 False 반환
                    # Return False if any prerequisite fails due to a cycle.
                    return False

            # 모든 선수 과목 탐색이 끝났으므로 순환 집합에서 제거합니다.
            # Remove the current node from the cycle set after exploring all prerequisites.
            cycle.remove(crs)

            # 탐색 완료된 노드는 결과에 추가합니다.
            # Add the current node to the result list after it is fully explored.
            res.append(crs)

            # 탐색이 성공적으로 완료되었음을 표시합니다.
            # Return True to indicate successful processing.
            return True

        # 모든 과목에 대해 DFS를 수행합니다.
        # Perform DFS for all courses.
        for c in range(numCourses):
            if not dfs(c):  # 싸이클 발견 시 빈 리스트 반환
                # Return an empty list if a cycle is detected.
                return []

        # 결과 리스트를 반환합니다.
        # Return the result list containing the order of courses.
        return res

 

최종(DFS 기반 위상 정렬)

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # prerequisites[i] = [a, b], b->a 순서로 수업
        # 수업 총개수: numCourses -> 0 ~ numCourses-1
        # return 수업듣는 순서, 모두 못들으면 return []
        adj = {}
        for i in range(numCourses):
            adj[i] = []

        for a, b in prerequisites:
            adj[b].append(a)

        visit = set() # 방문완료
        visiting = set() # 방문중
        res = [] # 방문순서

        def dfsCycleCheck(src):
            if src in visit: # 이미 방문했으면
                return True 
            if src in visiting: # 지금 방문중인데, 이미 방문중이라고 나오면, 순환싸이클있는것임
                return False

            visiting.add(src) # 방문중 표시
            for dst in adj[src]:
                # if dst in visit: # 후순위 과목이 이미 방문했으면, 
                #     return False # 싸이클 있는거
                if not dfsCycleCheck(dst): # 후순위 과목이 이미 방문했으면
                    return False
            visiting.remove(src)
            visit.add(src) # 방문 완료 표시
            res.append(src)
            return True

        for i in range(numCourses):
            dfsCycleCheck(i)