[위상정렬] 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

DFS로 

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        """
        prerequisites: 
        [a, b] => a 수강하려면. b 가 선수과목 

        preMap
        cource | pre
        0      | []
        1      | [0]
        이때, 과목 0은 pre 가 없으므로, 선수과목이 필요없는..
        """        
        # preMap, map each course to prereq list
        preMap = {i : [] for i in range(numCourses)} 

        # 해쉬맵 매핑
        for course, pre in prerequisites:
            preMap[course].append(pre)

        # visitSet = all courses along the curr DFS path
        visitSet = set()
        def dfs(crs):
            if crs in visitSet: # visit twice, curcle loof
                return False

            if preMap[crs] == []: # 선수과목이 필요없음
                return True

            visitSet.add(crs)
            for pre in preMap[crs]:
                if not dfs(pre): 
                    return False
            visitSet.remove(crs)

            # 여기까지 로직이 왔다면, 
            # preMap[crs] 는 만족한다는 것이니. 
            # 이후 해당 과목을 방문할 때 바로 True를 반환하여 
            # 추가적인 DFS 호출을 줄일 수 있음            
            preMap[crs] = [] 
            return True

        for crs in range(numCourses):
            if not dfs(crs): 
                return False
            
        return True

 

최종 코드

좋아요! 이 문제는 사이클이 있는지 확인하는 문제이고,
그래프 탐색(DFS or BFS) 으로 풀 수 있어요.
그래프를 인접 리스트(adj list) 로 표현해서 **사이클이 있으면 False, 없으면 True**를 리턴하는 구조입니다.

---

✅ 핵심 아이디어

• prerequisites = [[a, b]]는 b → a 방향의 의존성(edge) 을 의미
  → 즉, 과목 b를 먼저 들어야 a를 들을 수 있다
• 이를 인접 리스트로 그래프에 저장하고,
• DFS로 순환(cycle)이 있는지 탐색

---

✅ 인접 리스트 + DFS 풀이 (Python)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 선수과목 prerequisites[i] = [ai, bi] [듣고자하는 과목, 선수과목]
        # 순환구조가 아니면 True, 순환 구조이면 False

        # 그래프 구성: {과목번호: [그 과목을 듣기 위해 먼저 들어야 할 과목들]}
        preCourses = defaultdict(list) # {듣고자하는 과목: [선수과목, ]}
        for c, pre in prerequisites:
            preCourses[c].append(pre) # pre → c (pre를 듣고 나서 c 들을 수 있음)

        visit = set() # 순환 싸이클 확인용
        finished_course = set() # 순환 없다고 확인한 코스들. 즉, 완료된 코스들

        def dfs(course):
            if course in visit:
                return False # 순환 발생

            if course in finished_course:
                return True # 이미 완료된 코스
            
            visit.add(course) # 방문 추가
            for pre in preCourses[course]:
                if not dfs(pre): # 선수과목이 순환발생
                    return False # 순환 발생
            visit.remove(course) # 방문 해제

            finished_course.add(course) # 코스 완료 처리
            return True

        # 모든 과목을 dfs로 탐색
        for c in range(numCourses):
            if not dfs(c): # 순환 발생하면
                return False

        return True

 

우선은, 'DFS 인접행렬'로 푸는것 익히자!!

 

이번엔 이 문제를 BFS (Kahn’s Algorithm) 을 사용해서
위상 정렬 방식으로 푸는 방법을 알려드릴게요.

---

✅ 핵심 아이디어 (Kahn’s Algorithm = 위상 정렬):

• 진입 차수(in-degree): 각 노드로 들어오는 간선 수를 계산
  (→ 선행 과목이 몇 개인지)
• 진입 차수가 0인 노드들부터 큐에 넣고, 하나씩 꺼내면서
  연결된 노드들의 진입 차수를 줄여나감
• 모든 노드를 방문할 수 있다면 True,
  사이클이 있다면 일부 노드 진입 차수가 0이 되지 않아 큐에서 빠지지 않음 → False

---

✅ 코드 (Kahn's Algorithm using BFS):

from typing import List
from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)  # 인접 리스트
        in_degree = [0] * numCourses  # 각 노드의 진입 차수

        # 그래프 구성 + 진입 차수 계산
        for a, b in prerequisites:
            graph[b].append(a)     # b → a
            in_degree[a] += 1      # a의 진입 차수 1 증가

        # 진입 차수가 0인 과목들을 큐에 넣기 (선행 조건 없는 과목들)
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        taken = 0  # 수강 완료한 과목 수

        while queue:
            course = queue.popleft()
            taken += 1  # 이 과목 수강 완료

            # 이 과목을 들었기 때문에, 연결된 후속 과목들의 진입 차수 감소
            for neighbor in graph[course]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        # 전체 과목을 다 들었으면 True, 아니면 False (사이클 존재)
        return taken == numCourses

 

💡 예시:

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]

• 0 → 1, 0 → 2, 1 → 3, 2 → 3
• 위상 정렬 순서: 0 → 1,2 → 3
• 모두 수강 가능 → True

---

✅ 요약:

구성 요소	설명
graph	인접 리스트 (후속 과목 목록)
in_degree[]	각 과목의 선행 조건 개수
queue	지금 바로 들을 수 있는 과목들
taken	수강 완료한 과목 개수

---

DFS기반 위상정렬로 풀이

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # prerequisites[i] = [a, b]: 수업 듣는 순서 b->a
        # 모든 수업 들을수 있으면 return true
        # 그렇지 않으면, return false 그리고, 싸이클 감지되도 return false, 

        adj = {}
        for i in range(numCourses):
            adj[i] = []
        for a, b in prerequisites:
            adj[b].append(a) # src: b, dst: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 not dfsCycleCheck(dst): # 다음과목에서 싸이클 발견되면
                    return False # 싸이클 있음

            visiting.remove(src) # 현재 과목:방문중 해제
            visit.add(src) # 현재 과목:방문 완료 추가
            res.append(src) # post-order 로 결과 추가
            return True # 싸이클 없음 

        # 모든 과목에서 싸이클 있는지 확인
        for i in range(numCourses):
            if not dfsCycleCheck(i): # 싸이클 있으면
                return False

        res = res[::-1] # post-order 를 원래 순서로..
        # 그런데, res 결과의 개수가 총 코스 개수여야.. 모든 코스를 끝내는 거라서,
        # 안되면 return False
        return True if len(res) == numCourses else False