a-087-course-schedule2026-08-14mediumleetcode #207neetcode150

코스 스케줄

#depth-first-search#breadth-first-search#graph#topological-sort#directed-acyclic-graph

문제

· problem

P.a-087-course-schedule

코스 스케줄

총 numCourses개의 강좌를 수강해야 하며, 강좌는 0부터 numCourses - 1까지 표시됩니다. prerequisites 배열이 주어지는데, prerequisites[i] = [ai, bi]는 ai 강좌를 수강하려면 먼저 bi 강좌를 완료해야 한다는 의미입니다. 예를 들어, [0, 1] 쌍은 강좌 0을 수강하려면 먼저 강좌 1을 완료해야 한다는 뜻입니다. 모든 강좌를 완료할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

제약

· 1 ≤ numCourses ≤ 2000
· 0 ≤ prerequisites.length ≤ 5000
· prerequisites[i].length = 2
· All prerequisite pairs are unique

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

2
[[1,0]]

true

example 2input → output

2
[[1,0],[0,1]]

false

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
선행과목 쌍 [a, b]의 의미를 정확히 이해했나요?
☐
순환이 있으면 왜 모든 강좌를 완료할 수 없나요?
☐
강좌는 여러 개의 선행과목을 가질 수 있나요?
☐
DFS 방식과 BFS(위상정렬) 방식 중 어느 것이 더 효율적인가요?
☐
모든 강좌를 한 번 이상 DFS로 시작해야 하나요?
☐
visited와 visiting 두 개의 상태를 모두 추적해야 하나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 그래프 초기화: 각 강좌별 선행과목 목록

○

preMap = {i: [] for i in range(numCourses)}

○

preMap = {}

○

preMap = [[] for _ in range(numCourses)]

step 2· 그래프 구성: 선행과목 관계 추가│ 중첩

○

for crs, pre in prerequisites:

○

preMap[pre].append(crs)

○

preMap[crs] = pre

step 3· 순환 감지 준비: 현재 경로 추적

○

visiting = set()

○

visited = set()

○

visiting = {i: 0 for i in range(numCourses)}

step 4· 순환 확인: 현재 경로에서 강좌를 만났는가?│ 중첩

○

if crs in visiting:

○

if crs in visited:

○

if preMap[crs] == []: return True

step 5· 기저 사례: 선행과목이 없으면 강좌 완료 가능│ 중첩

○

if preMap[crs] == []:

○

if len(preMap[crs]) == 0:

○

if not preMap[crs]:

step 6· 경로 기록: 현재 강좌를 방문 중으로 표시│ 중첩

○

visiting.add(crs)

○

visiting.add(crs) after recursion

○

visited.add(crs)

step 7· 역추적: 강좌를 경로에서 제거하고 완료 표시│ 중첩

○

visiting.remove(crs)

○

# visiting.remove(crs)

○

preMap[crs] = -1

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        # dfs

        preMap = {i: [] for i in range(numCourses)}

        # map each course to : prereq list

        for crs, pre in prerequisites:

            preMap[crs].append(pre)

        visiting = set()

        def dfs(crs):

            if crs in visiting:

                return False

            if preMap[crs] == []:

                return True

            visiting.add(crs)

            for pre in preMap[crs]:

                if not dfs(pre):

                    return False

            visiting.remove(crs)

            preMap[crs] = []

            return True

        for c in range(numCourses):

            if not dfs(c):

                return False

        return True

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

2
[[1,0]]

→

true

case 2

2
[[1,0],[0,1]]

→

false

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.