[위상정렬: 싸이클 탐지] 1462. Course Schedule IV

1462. Course Schedule IV

 

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # numCourses: 전체 수업 개수 (0부터 numCourses-1까지 번호가 매겨짐)
        # prerequisites[i] = [a, b]: 수업 a를 먼저 들어야 b를 들을 수 있음 (a → b)
        # queries[j] = [u, v]: u가 v의 직접 또는 간접 선행 과목인지 확인해야 함

        # 1. 인접 리스트 (adjacency list)와 reachable 딕셔너리 초기화
        # adj[i]: 과목 i를 들은 후 들을 수 있는 과목 리스트
        # reachable[i]: 과목 i를 들은 후 도달 가능한 모든 과목을 저장하는 set
        adj = {}
        reachable = {}
        for i in range(numCourses):
            adj[i] = []         # i번 과목의 다음 과목들 리스트 초기화
            reachable[i] = set()  # i번 과목에서 도달 가능한 과목들을 저장할 집합 초기화

        # 2. prerequisites를 기반으로 인접 리스트 채우기
        for a, b in prerequisites:
            adj[a].append(b)  # a를 들으면 b를 들을 수 있으므로, adj[a]에 b 추가

        # 3. DFS 정의: start 과목에서 시작하여 방문 가능한 모든 과목을 reachable[start]에 저장
        def dfs(cur, start):
            for nxt in adj[cur]:  # 현재 과목(cur)에서 갈 수 있는 다음 과목들 순회
                if nxt not in reachable[start]:  # 아직 start에서 도달 가능한 목록에 없다면
                    reachable[start].add(nxt)    # 도달 가능한 과목으로 추가
                    dfs(nxt, start)              # 다음 과목에서 다시 탐색

        # 4. 모든 과목에 대해 DFS 수행하여 각 과목에서 도달 가능한 과목들 계산
        for i in range(numCourses):
            dfs(i, i)  # i번 과목을 시작점으로 dfs 수행하여 reachable[i] 채움

        # 5. 주어진 쿼리 처리
        res = []
        for u, v in queries:  # u가 v의 선행과목인지 확인
            if v not in reachable[u]:
                res.append(False)  # u에서 v까지 도달할 수 없으면 False
            else:
                res.append(True)   # u에서 v까지 도달 가능하면 True
        return res  # 모든 쿼리에 대한 결과 반환

 

🧠 핵심 요약:

• reachable[u]은 과목 u를 들으면 직접 또는 간접적으로 들을 수 있는 모든 과목들.
• 각 쿼리 [u, v]에 대해 v in reachable[u]만 확인하면 되므로 매우 효율적입니다.
• 시간 복잡도는 최악의 경우 O(N^2)까지 갈 수 있으나, 수업 수가 적당히 제한된 경우 매우 빠릅니다.

https://youtu.be/cEW05ofxhn0