Course Schedule
numCourses개의 강의가 있으며, 번호는 0부터 numCourses-1까지입니다. prerequisites에 있는 각 쌍 [a, b]는 강의 a를 시작하기 전에 강의 b를 끝내야 한다는 뜻입니다. 모든 강의를 끝낼 수 있는 순서가 있으면 true를 반환하고, 그런 순서가 없으면 false를 반환하세요.
함수
- numCoursesinteger
- 강의 수
- prerequisitesinteger-2d-array
- 각각 과목 b가 과목 a보다 먼저 와야 함을 의미하는 [a, b] 쌍
- 반환값boolean
- 모든 과정을 마칠 수 있으면 true, 그렇지 않으면 false
제약 조건
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- 각 쌍
[a, b]에서0 ≤ a, b < numCourses입니다. - 어떤 쌍도 두 번 나타나지 않습니다.
- A 쌍에 같은 과목이 두 번 나타날 수 있습니다.
[a, a]이 과목은 자신을 먼저 들어야 하므로 절대 수강할 수 없습니다.
예제
- 입력
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- 출력
- true
- 설명
- 과목 0에는 선수 과목이 없으므로 가장 먼저 수강합니다. 그러면 과목 1을 수강할 수 있고, 과목 1을 수강하면 과목 2와 3을 모두 수강할 수 있으므로 0, 1, 2, 3 순서가 가능합니다.
- 입력
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- 출력
- false
- 설명
- 과목 0은 2를 기다리고, 과목 2는 1을 기다리며, 과목 1은 0을 기다립니다. 세 과목이 서로를 기다리며 순환하므로, 그중 어느 과목도 가장 먼저 수강할 수 없습니다.
제출 시 숨은 테스트 +20개
후속 질문
각 과목의 선수 과목을 이전 학기에 이수했다면, 한 학기에 몇 개의 과목이든 수강할 수 있습니다. 모든 과목을 이수하는 데 필요한 최소 학기 수는 몇 학기인가요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
각 과목을 점으로 그리고 각 쌍
[a, b]을b에서a로 향하는 화살표로 나타내 보세요. 이 그림에서 어떤 모양이 있으면 과정을 끝내는 것이 불가능할까요?화살표가 순환하는 형태입니다. 순환에 있는 모든 과목은 같은 순환에 있는 다른 과목을 기다리므로, 어느 과목도 먼저 시작할 수 없습니다. 그래프에 사이클이 있는지가 관건입니다.
각 과목이 아직 기다리고 있는 선수 과목의 수를 세세요. 선수 과목 수가 0인 과목들을 큐에 넣고, 하나를 꺼낼 때마다 그 과목을 기다리는 모든 과목의 수를 줄이세요. 큐에 들어가는 과목의 수가
numCourses보다 적다면 사이클이 있습니다.
풀이
쌍들을 V = numCourses개의 노드와 E = prerequisites.length개의 간선을 가진 방향 그래프로 바꾸세요. 각 쌍 [a, b]에 대해 화살표 b → a를 하나씩 그립니다. 그래프에 사이클이 없을 때에만 모든 과정을 마칠 수 있습니다. Kahn의 알고리즘은 학생이 계획을 세우는 방식으로 이를 판단합니다. 선수 과목을 모두 이수한 과목을 계속 수강하면서, 과목이 먼저 바닥나는지 아니면 선택지가 먼저 바닥나는지 확인합니다.
무료 강좌를 하나하나, 라운드마다 수강하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
학생이라면 어떻게 계획할지 생각해 보세요. 각 라운드마다 아직 이수하지 않은 모든 과목을 살펴봅니다. 선수 과목을 모두 이수했다면 해당 과목을 이수합니다. 한 라운드에서 아무 과목도 이수하지 않을 때까지 반복합니다. 그때 모든 과목을 이수했다면 답은 참입니다.
진행이 멈춘 라운드가 거짓을 뜻하는 이유: 한 라운드에서 아무 과목도 이수하지 못하면, 남은 모든 과목에는 남아 있는 선수 과목이 있습니다. 남은 과목 중 하나에서 시작해, 아직 이수하지 않은 선수 과목 중 하나로 계속 이동합니다. 이동을 계속해도 끝나지 않고, 과목 수는 한정되어 있으므로 이미 방문한 과목으로 돌아오게 됩니다. 이것은 사이클이며, 그 안의 과목들은 서로를 기다리며 영원히 이수되지 않습니다.
이 방법은 정확하지만, 매 라운드마다 모든 과목 쌍과 모든 과목을 다시 살펴보고, 한 라운드에서 과목을 하나만 이수할 수도 있습니다. 각 과목이 바로 앞 과목을 필요로 하는 5,001개 과목의 연쇄는 5,000회가 넘는 라운드가 필요합니다. 과목이 100,000개라면 확인 횟수는 약 5 × 10^8회이며, 그중 거의 전부는 상태가 바뀌지 않은 과목에 대한 확인입니다.
알고리즘
- 모든 과목을 수강하지 않은 것으로 표시합니다.
- 어떤 쌍에서 수강하지 않은 선행 과목을 지정한 과목은 수강 불가로 표시합니다.
- 이미 수강했거나 수강 불가로 표시되지 않은 모든 과목을 수강합니다.
- 이번 라운드에서 아무 과목도 수강하지 않았다면 중단합니다. 그렇지 않으면 2단계로 돌아갑니다.
- 모든 과목을 수강했으면 true를 반환합니다.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCourses세 가지 상태를 사용하는 깊이 우선 탐색
핵심 아이디어
사이클은 시작한 곳으로 되돌아오는 경로입니다. 깊이 우선 탐색은 현재 따라가고 있는 경로에 어떤 과목이 있는지 기억하여 사이클을 찾습니다. 모든 과목에 세 가지 상태를 부여하세요. 방문하지 않음, 현재 경로에 있음, 완료됨.
한 과목에서 화살표를 따라 그 과목을 기다리는 과목들로 이동하세요. 과목에 들어갈 때 "현재 경로에 있음"으로 표시하고, 해당 과목에서 나가는 모든 화살표를 탐색한 뒤 되돌아올 때 "완료됨"으로 표시하세요. 현재 경로에 있는 과목으로 향하는 화살표는 빙빙 돌아 제자리로 왔다는 뜻입니다. false를 반환하세요. 완료된 과목으로 향하는 화살표는 안전합니다. 그 과목에서 도달할 수 있는 모든 곳을 확인했고 사이클이 없음을 알기 때문에 건너뛰면 됩니다. 각 과목에는 한 번씩 들어가고, 각 화살표는 한 번씩 따라갑니다.
상태를 두 개만 두는 것으로는 충분하지 않습니다. 다이아몬드 형태의 0 → 1, 0 → 2, 1 → 3, 2 → 3에서 탐색은 2를 통해 과목 3에 두 번째로 도달하지만, 그때 3은 이미 완료된 상태이지 현재 경로에 있는 상태가 아니며 사이클도 없습니다. 현재 경로로 돌아가는 화살표만 루프를 만듭니다.
직접 스택을 사용하고 각 과목마다 다음에 탐색할 화살표의 위치를 저장하여 탐색을 작성하세요. 재귀 버전이 더 짧지만, 과목이 5,000개인 사슬에서는 호출 깊이가 5,000이 됩니다.
알고리즘
- 각 과목에 대해 해당 과목을 기다리는 과목 목록을 만듭니다.
- 방문하지 않은 각 과목에 대해 경로에 표시하고 스택에 넣습니다.
- 스택의 맨 위를 확인합니다. 더 이상 화살표가 없으면 완료로 표시하고 스택에서 꺼냅니다. 그렇지 않으면 다음 화살표를 따라갑니다.
- 화살표가 경로에 있는 과목을 가리키면 false를 반환합니다. 방문하지 않은 과목을 가리키면 해당 과목을 경로에 표시하고 스택에 넣습니다.
- 모든 과목이 완료되면 true를 반환합니다.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return True칸 알고리즘
핵심 아이디어
첫 번째 접근 방식에서는 변경되지 않은 과목을 다시 확인하느라 라운드마다 시간을 낭비합니다. 과목은 마지막 선수 과목을 이수하는 순간에만 이수 가능 상태가 됩니다. 따라서 각 과목에 대해 아직 이수해야 하는 선수 과목의 수, 즉 진입 차수를 셉니다. 어떤 과목을 이수하면 그 과목을 기다리는 모든 과목의 수를 줄입니다. 수가 0으로 줄어들면 해당 과목을 지금 이수할 수 있으므로 큐에 넣습니다.
처음부터 수가 0인 모든 과목을 큐에 넣고, 큐가 빌 때까지 큐에서 과목을 꺼내 이수합니다. 첫 번째 예시에서 과목 0부터 3까지의 수는 처음에 0, 1, 1, 1입니다. 0을 이수하면 과목 1의 수가 0으로 줄어듭니다. 1을 이수하면 과목 2와 3의 수가 0으로 줄어듭니다. 네 과목을 모두 이수하므로 답은 true입니다. 각 과목은 큐에 최대 한 번 들어가고, 각 쌍은 수를 한 번씩만 줄이므로 작업량은 O(V + E)입니다.
남은 과목이 순환을 의미하는 이유는 다음과 같습니다. 과목 a를 이수하지 않은 상태에서 큐가 비었다면, a의 수는 0보다 크므로 선수 과목 중 하나인 b도 이수되지 않은 상태입니다. b에도 같은 논리가 적용되는 식으로 이어집니다. 과목에서 이수하지 않은 선수 과목으로 계속 따라가면 멈추지 않으므로, 결국 어떤 과목에 다시 도달하게 되고 이는 순환입니다. 두 번째 예시에서는 처음부터 수가 0인 과목이 없으므로 큐가 빈 상태로 시작하고, 세 과목 중 어느 것도 이수되지 않습니다.
역방향도 성립합니다. 순환에 속한 과목은 같은 순환에 속한 다른 과목을 기다리므로, 그 과목이 이수되기 전에 해당 과목의 수가 0이 될 수 없으며, 순환에 속한 과목 중 어느 것도 먼저 이수되지 않습니다. 따라서 "모든 과목 이수"와 "순환 없음"은 같은 말입니다. 덤으로, 과목이 큐에서 나온 순서는 유효한 수강 일정입니다.
알고리즘
- 각 [a, b] 쌍에 대해, b를 기다리는 과목 목록에 a를 추가하고 a의 진입 차수에 1을 더합니다.
- 진입 차수가 0인 모든 과목을 큐에 넣습니다.
- 큐에서 과목 하나를 꺼내 세고, 그 과목을 기다리는 모든 과목의 진입 차수를 낮춥니다. 진입 차수가 0이 된 과목은 각각 큐에 추가합니다.
- 큐가 비었을 때, 개수가
numCourses와 같은지 반환합니다.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
함정과 경계 사례
대부분의 버그는 쌍의 방향을 혼동하거나, 사이클 검사를 지나치게 엄격하게 하거나, 어떤 쌍에도 나타나지 않는 과목에서 발생합니다.
- 방향을 혼동하는 경우.
[a, b]는 b가 먼저 온다는 뜻이므로, 화살표는 b에서 a로 향하고 a의 진입 차수가 증가합니다. 한 방향으로 목록을 만들고 다른 방향으로 진입 차수를 세면 알고리즘이 제대로 작동하지 않습니다. - 어떤 쌍에도 나타나지 않는 과목을 빠뜨리는 경우.
numCourses = 5이고 쌍이[4, 3]하나뿐이어도 과목 0, 1, 2도 여전히 포함됩니다. 쌍에 등장한 과목만이 아니라 진입 차수가 0인 모든 과목을 큐에 넣고 시작하세요. - 과목이 자기 자신의 선수 과목인 경우,
[2, 2]. 길이가 1인 사이클입니다. 진입 차수가 절대 0이 되지 않으므로 답은 false입니다. - 깊이 우선 탐색에서 세 가지 상태 대신 두 가지 상태만 사용하는 경우. 다이아몬드 구조 0 → 1, 0 → 2, 1 → 3, 2 → 3에서는 과목 3에 두 번 도달합니다. "방문함"만 추적하면 이 상황이 사이클처럼 보입니다. 현재 경로로 되돌아오는 화살표만이 루프를 만듭니다.
- 긴 연결에서 재귀를 사용하는 경우. 과목 5,000개의 연결은 호출 깊이가 5,000까지 이르러 Python의 기본 제한인 1,000을 넘습니다.
- 큐가 비었을 때 수강한 과목 수와
numCourses를 비교하지 않고 true를 반환하는 경우.
자주 묻는 질문4
Course Schedule 문제의 시간 복잡도는 얼마인가요?
O(V + E)이며, V는 과목 수이고 E는 쌍의 수입니다. Kahn 알고리즘이나 깊이 우선 탐색을 사용할 수 있습니다. 목록을 만들 때 각 쌍을 한 번씩 읽고, 각 과목은 최대 한 번 큐에 들어가며, 각 쌍은 카운트를 한 번씩 감소시킵니다. 목록과 카운트에는 O(V + E)의 공간이 필요합니다.
칸의 알고리즘에서 처리되지 않고 남은 과목이 있다는 것은 왜 사이클이 있다는 뜻인가요?
과목의 개수가 한 번도 0에 도달하지 않은 경우에만 해당 과목이 남으므로, 선수 과목 중 적어도 하나도 남아 있습니다. 과목에서 과목으로 이어지는 대기 과정을 따라가 보세요. 매 단계마다 또 다른 남은 과목에 도달하고, 과목의 수는 유한하므로 따라가다 보면 반드시 이미 거친 과목으로 돌아오게 됩니다. 두 번 방문한 지점 사이의 구간이 사이클입니다.
Course Schedule에는 BFS와 DFS 중 무엇을 사용해야 할까요?
둘 다 O(V + E) 시간에 실행됩니다. 너비 우선 방식인 칸 알고리즘은 재귀 깊이를 걱정할 필요가 없고, 유효한 과목 순서를 자동으로 제공합니다. 세 가지 상태를 사용하는 깊이 우선 탐색도 마찬가지로 빠르며, 사이클도 보고해야 할 때 자연스러운 선택입니다. 스택에 있는 과목들이 사이클을 이루기 때문입니다.
위상 정렬이란 무엇인가요?
모든 화살표가 앞쪽을 가리키는 방향 그래프 노드의 순서입니다. 여기서는 각 선수 과목이 그 과목을 필요로 하는 과목보다 먼저 오는 과목 순서를 뜻합니다. 그래프에 사이클이 없을 때에만 존재하며, Kahn's algorithm이 과목을 선택하는 순서가 그중 하나입니다. Course Schedule은 위상 정렬 순서가 존재하는지 묻습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def canFinish(numCourses, prerequisites):
# 여기에 코드를 작성하세요케이스 1
케이스 2
입력
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
기대값
true