a-088-course-schedule-ii2026-08-15mediumleetcode #210neetcode150

강의 일정 II

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

↗ leetcode #210 · a-088-course-schedule-ii

문제

· problem

P.a-088-course-schedule-ii

강의 일정 II

총 numCourses개의 강의를 이수해야 합니다. 강의는 0부터 numCourses-1로 번호가 매겨져 있습니다. prerequisites 배열이 주어지는데, prerequisites[i] = [a, b]는 강의 a를 들으려면 먼저 강의 b를 완료해야 함을 의미합니다. 예를 들어, [0, 1]은 강의 0을 들으려면 먼저 강의 1을 들어야 합니다는 뜻입니다. 모든 강의를 마칠 수 있도록 강의를 들어야 하는 순서를 반환하세요. 가능한 순서가 여러 개라면 그 중 어느 것이든 반환해도 됩니다. 모든 강의를 마칠 수 없다면 빈 배열을 반환하세요.

제약

· 1 ≤ numCourses ≤ 2000
· 0 ≤ prerequisites.length ≤ numCourses × (numCourses - 1)
· prerequisites[i].length == 2
· 0 ≤ a_i, b_i < numCourses

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

입출력 예시

example 1input → output

2
[[1,0]]

[0,1]

example 2input → output

4
[[1,0],[2,0],[3,1],[3,2]]

[0,2,1,3]

example 3input → output

1
[]

[0]

사전 사고

· pre-solve

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

☐
prerequisites[i] = [a, b]에서 어느 강의를 먼저 들어야 하나요?
☐
모든 강의를 들을 수 없는 경우는 언제인가요?
☐
여러 개의 유효한 순서가 있을 때, 어떤 것을 반환해야 하나요?
☐
선수 과목이 없는 강의는 어디든 배치할 수 있나요?
☐
탐욕 알고리즘으로 먼저 들을 수 있는 강의를 선택하면 항상 해결되나요?
☐
반환 배열의 강의들이 정렬된 순서여야 하나요?

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

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

논리 구조

· logic

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

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

step 1· 그래프 구성

○

prereq = {c: [] for c in range(numCourses)}

○

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

○

prereq = defaultdict(list)

step 2· 상태 추적 초기화

○

visit, cycle = set(), set()

○

visited = set()

○

visit, cycle = [False]*numCourses, [False]*numCourses

step 3· 현재 경로의 사이클 감지│ 중첩

○

if crs in cycle:

○

if crs in visit: return False

○

if not crs in cycle: return False

step 4· 방문 완료 노드 건너뛰기│ 중첩

○

if crs in visit:

○

if crs in cycle: return True

○

if crs not in visit: return True

step 5· 현재 탐색 경로에 표시│ 중첩

○

cycle.add(crs)

○

visit.add(crs)

○

cycle.append(crs)

step 6· 선수 과목 재귀 탐색│ 중첩

○

for pre in prereq[crs]:

○

for pre in visit: dfs(pre)

○

all(dfs(pre) for pre in prereq[crs])

step 7· 역추적 및 결과 기록│ 중첩

○

visit.add(crs)

○

output.append(crs); cycle.remove(crs)

○

cycle.remove(crs); visit.add(crs)

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

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

문제풀이 · 트레이스

· solve

solution.py

class Solution:

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

        prereq = {c: [] for c in range(numCourses)}

        for crs, pre in prerequisites:

            prereq[crs].append(pre)

        output = []

        visit, cycle = set(), set()

        def dfs(crs):

            if crs in cycle:

                return False

            if crs in visit:

                return True

            cycle.add(crs)

            for pre in prereq[crs]:

                if dfs(pre) == False:

                    return False

            cycle.remove(crs)

            visit.add(crs)

            output.append(crs)

            return True

        for c in range(numCourses):

            if dfs(c) == False:

                return []

        return output

머릿속 dry-run 케이스

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

case 1

2
[[1,0]]

→

[0,1]

case 2

4
[[1,0],[2,0],[3,1],[3,2]]

→

[0,2,1,3]

case 3

1
[]

→

[0]

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