Graphs(싸이클탐지): 207. Course Schedule ★★★

207. Course Schedule

 

https://youtu.be/EgI5nU9etnU?si=bTi7R-EQNB2-fzZ2

 

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 선수 과목 정보를 저장할 딕셔너리를 초기화합니다.
        # Initialize a dictionary to store prerequisite information.
        preMap = {i: [] for i in range(numCourses)}

        # prerequisites 리스트의 각 쌍 [course, pre]에 따라 preMap을 채웁니다.
        # Fill the preMap with prerequisites based on the input list.
        for course, pre in prerequisites:
            preMap[course].append(pre)
        
        # 방문한 노드를 추적하기 위한 집합(DFS 경로상에서만 사용).
        # A set to track visited nodes (used only in the current DFS path).
        visit = set()

        # DFS 함수 정의
        # Define the DFS function
        def dfs(course):
            # 이미 현재 경로에 포함된 노드를 다시 방문하면 싸이클이 발생한 것
            # If the node is already in the current path, it means there's a cycle.
            if course in visit:
                return False
            
            # 해당 과목의 선수 과목이 없다면 True 반환 (기저 조건)
            # If the course has no prerequisites, return True (base case).
            if preMap[course] == []:
                return True

            # 현재 노드를 방문 집합에 추가
            # Add the current node to the visited set.
            visit.add(course)

            # 현재 과목의 선수 과목들을 DFS로 탐색
            # Recursively check prerequisites of the current course.
            for pre in preMap[course]:
                if not dfs(pre):  # 선수 과목 충족 불가 시 False 반환
                    return False
            
            # 현재 노드의 탐색이 끝나면 방문 집합에서 제거
            # Remove the current node from the visited set after exploration.
            visit.remove(course)

            # 여기까지 로직이 왔다면, preMap[course]는 선수 과목 조건을 만족한다는 뜻입니다.
            # 이후 해당 과목을 다시 방문할 때 바로 True를 반환하여 추가적인 DFS 호출을 줄일 수 있습니다.
            # If the logic reaches here, it means preMap[course] satisfies the prerequisite condition.
            # This allows us to return True immediately for future visits, avoiding redundant DFS calls.
            preMap[course] = []

            return True

        # 모든 과목에 대해 DFS 탐색 수행
        # Perform DFS for all courses.
        for cur in range(numCourses):
            if not dfs(cur):  # 한 과목이라도 싸이클이 있으면 False 반환
                return False

        # 모든 과목을 문제없이 완료할 수 있으면 True 반환
        # If all courses can be completed, return True.
        return True

 

https://youtu.be/bG9IObCN-tg?si=L3tYUagjaRLdYDjx

 

BFS로 

from collections import deque
from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        """
        BFS를 사용하여 코스 스케줄 문제를 해결합니다. 순환(cycle)이 있는 경우 False를 반환하고, 모든 코스를 완료할 수 있으면 True를 반환합니다.
        """
        # 그래프를 후속 -> 선수 과목으로 구성합니다.
        # Create an adjacency list where each course points to its prerequisites.
        graph = {i: [] for i in range(numCourses)}  # 모든 코스를 초기화

        for after, pre in prerequisites:
            graph[after].append(pre)  # 후속 과목 -> 선수 과목

        # 방문한 코스를 저장하기 위한 집합
        # A set to track visited courses.
        visit = set()

        # 진입 차수가 없는 노드를 큐에 추가합니다.
        # Add courses with no prerequisites to the queue.
        q = deque([i for i in range(numCourses) if not graph[i]])

        while q:
            curr_course = q.popleft()

            # 현재 코스를 방문으로 표시
            # Mark the current course as visited.
            visit.add(curr_course)

            # 모든 코스의 선수 과목에서 현재 코스를 제거
            # Remove the current course from other course prerequisites.
            for course in range(numCourses):
                if curr_course in graph[course]:
                    graph[course].remove(curr_course)

                    # 선수 과목이 더 이상 없으면 큐에 추가
                    # If no prerequisites remain, add the course to the queue.
                    if not graph[course] and course not in visit:
                        q.append(course)

        # 방문한 코스 수가 전체 코스 수와 같으면 True 반환
        # Return True if all courses are visited, otherwise False.
        return len(visit) == numCourses