LeetCode/Grind169
210. Course Schedule II ☆☆★★★★ DFS, BFS 둘다 풀수있게. BFS 꼭 숙지!!
hyunkookim
2025. 5. 1. 09:07
**Topological Sort (위상 정렬)**을 이용해 해결해야 하는 그래프 문제입니다.
한 문장씩 간단하게 설명해드릴게요.
✅ 문제 설명 (한 문장씩 해석)
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1.
👉 0번부터 numCourses - 1번까지의 수업이 있으며, 총 numCourses개입니다.
You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
👉 prerequisites[i] = [a, b]는 b를 먼저 들어야 a를 들을 수 있다는 뜻입니다. 즉, b → a 선행 조건입니다.
Return the ordering of courses you should take to finish all courses.
👉 모든 수업을 들을 수 있는 순서를 배열로 리턴하세요.
If there are many valid answers, return any of them.
👉 가능한 순서가 여러 개라면 아무거나 하나 리턴해도 됩니다.
If it is impossible to finish all courses, return an empty array.
👉 만약 사이클이 있어서 전부 들을 수 없다면, []을 리턴해야 합니다.
🧠 요약하면
- Directed graph 문제이고,
- 사이클이 없고, 모든 노드를 방문할 수 있는 topological order를 구해야 해요.
- 사이클이 존재하면 [] 리턴!
📌 사용 가능한 알고리즘
✅ DFS + cycle detection
- 시간복잡도: O(V + E)
- 방향 그래프를 DFS로 탐색하면서 사이클이 있는지 체크
✅ Kahn’s Algorithm (BFS 기반 위상 정렬)
- in-degree = 0인 노드부터 시작
- 점점 in-degree 줄이면서 순서 정리
예시 다시 정리
입력:
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]→ 가능한 순서 중 하나: [0,1,2,3]
→ 또는 [0,2,1,3]도 OK
1차 내 코드
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# labeled from 0 to numCourses - 1
# prerequisites[i] = [ai, bi] => bi 듣고 ai
# 수업듣는 순서 리턴, 만약 사이클 있으면 [] 리턴
adj = {}
start = set()
for i in range(numCourses):
adj[i] = []
start.add(i)
if not prerequisites: # 비었으면
return list(start)
for a, b in prerequisites:
adj[b].append(a)
if a in start:
start.remove(a)
for k, v in adj.items():
print (k, v)
print(start)
if not start: # 시작점 없으면
return []
visited = set() # 방문 완료
visiting = set() # 방문 중
self.sub = []
def isCycleCheck(cur):
if cur in visited: # 싸이클 없으므로
return False
if cur in visiting:
return True # 싸이클 있으니깐
visiting.add(cur)
for nei in adj[cur]:
if isCycleCheck(nei): # 싸이클 있으면
return True
visiting.remove(cur)
visited.add(cur) # 싸이클 없었으니
self.sub.append(cur)
return False
res = []
for s in start:
self.sub = []
if isCycleCheck(s): # 싸이클 있으면
return []
if len(self.sub) == numCourses: # 모든 수업 다 못들으면, 굳이 추가할필요가.
res.append(self.sub[::-1]) # 순서 거꾸로
print(res)
return res[0] if len(res) >0 else []
코드를 잘 작성하셨어요! 전체적인 구조는 맞고, DFS 기반 위상 정렬 + 사이클 체크를 잘 구현하고 있습니다.
하지만 두 가지 핵심 오류로 인해 Course Schedule II 문제의 요구 조건을 정확히 만족하지 못해요.
❌ 문제점 1: 모든 노드를 탐색하지 않음 (start만 탐색)
for s in start:
...- 이 방식은 indegree == 0인 시작점들만 탐색하는데,
연결되지 않은 노드나 start에 포함되지 못한 노드가 있을 경우, 그 노드는 아예 방문하지 않게 됩니다.
🔎 예시:
numCourses = 3
prerequisites = [[1, 0]]- start = {0, 2} (2는 고립된 노드)
- 그런데 start에만 의존하면 2가 포함되지 않을 수도 있음
- 결과적으로 len(res[0]) != numCourses → ❌ 불완전한 경로
✅ 모든 노드에 대해 isCycleCheck()를 호출해야 안전합니다.
❌ 문제점 2: 결과 res[0]만 반환
res = []
for s in start:
self.sub = []
if isCycleCheck(s):
return []
...
res.append(self.sub[::-1])
return res[0] if len(res) > 0 else []- res에 여러 개의 sub list가 생기는데, 단 하나만 (res[0]) 반환합니다.
- 그런데 위상 정렬에서는 모든 노드를 하나의 배열로 이어 붙여야 합니다.
✅ 예:
res = [[0,1], [2], [3,4]]
→ 정답은 [0,1,2,3,4]여야 합니다
→ 지금은 res[0]만 반환하니 [0,1]만 나감 → ❌
✅ 수정해야 할 부분
1. start 말고 range(numCourses) 전체를 돌기
for i in range(numCourses):
if i not in visited:
if isCycleCheck(i):
return []2. self.sub 대신 전체 결과 리스트에 누적
res = []
def isCycleCheck(cur):
...
res.append(cur) # 싸이클 없을 때 방문 완료 시 추가→ 그리고 마지막에 res[::-1]을 반환
✅ DFS + cycle detection
- 시간복잡도: O(V + E)
- 방향 그래프를 DFS로 탐색하면서 사이클이 있는지 체크
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# labeled from 0 to numCourses - 1
# prerequisites[i] = [ai, bi] => bi 듣고 ai
# 수업 듣는 순서 리턴, 만약 사이클 있으면 [] 리턴
if not prerequisites: # 비었으면 선행 조건 없음 → 아무 순서나 가능
return [i for i in range(numCourses)]
adj = {}
for i in range(numCourses):
adj[i] = []
for a, b in prerequisites:
adj[b].append(a) # b → a: b 듣고 a 듣기
visited = set() # 방문 완료한 노드
visiting = set() # 현재 경로에서 방문 중인 노드
res = []
def isCycleCheck(cur):
if cur in visited: # 이미 처리된 노드면 싸이클 없음
return False
if cur in visiting: # 현재 경로에 있는데 또 방문 → 싸이클 발생
return True
visiting.add(cur)
for nei in adj[cur]:
if isCycleCheck(nei): # 자식 노드에서 싸이클 발견 시
return True
visiting.remove(cur)
visited.add(cur)
res.append(cur) # post-order로 추가 (처리 완료 후)
return False
"""
싸이클 없어도, 분리된 그래프 여러 개로 구성되어 있을 수 있기 때문에
모든 노드를 다 돌아야 하고, 그래서 start 노드 루틴은 필요 없음
"""
for node in range(numCourses):
if node not in visited:
if isCycleCheck(node): # 싸이클이 있으면 수강 불가
return []
"""
dfs + 사이클 탐지 로직에서는 위상정렬할 때
후위순회(post-order) 결과를 뒤집어야 올바른 순서가 됨
예: A -> B 라면, B를 먼저 res에 담고 A가 뒤에 담김 → 역순 필요
"""
return res[::-1]✅ 시간 복잡도: O(V + E)
- V = 노드 수 = numCourses
- E = 간선 수 = len(prerequisites)
이유:
- 각 노드를 최대 한 번 방문하고 (visited)
- 각 간선을 정확히 한 번 순회 (for nei in adj[cur])
- DFS로 모든 연결 컴포넌트를 탐색하므로 전체 그래프를 한 번 순회
✅ 공간 복잡도: O(V + E)
구성 요소별로 보면:
- adj: 인접 리스트 → O(E)
- visited, visiting: 노드 개수만큼 → O(V)
- res (위상 정렬 결과): 길이 V → O(V)
- 재귀 호출 스택: 최악 O(V) 깊이까지 쌓일 수 있음
➡️ 총합: O(V + E)
✅ Kahn’s Algorithm (BFS 기반 위상 정렬)
- in-degree = 0인 노드부터 시작
- 점점 in-degree 줄이면서 순서 정리
✅ 핵심 개념 (Kahn’s Algorithm)
- in-degree(진입 차수) 배열을 만든다.
→ 각 노드가 "얼마나 많은 수업을 선행으로 기다리는지" 저장 - in-degree가 0인 노드부터 큐에 넣고,
→ 큐에서 하나씩 꺼내며 인접 노드들의 in-degree를 줄인다. - 줄인 결과 in-degree가 0이 된 노드는 다시 큐에 넣는다.
- 모든 노드를 꺼냈다면 → 정상적인 수강 순서
하나라도 남았다면 → 사이클 존재 (return [])
✅ Python 코드 (주석 포함)
from collections import defaultdict, deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# 1. 그래프 만들기
adj = defaultdict(list) # b → a: b 듣고 나서 a
in_degree = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a)
in_degree[a] += 1 # a는 b를 기다려야 함
# 2. in-degree가 0인 수업부터 큐에 넣기 (즉, 바로 들을 수 있는 수업들)
q = deque([i for i in range(numCourses) if in_degree[i] == 0])
res = []
# 3. BFS 시작
while q:
course = q.popleft()
res.append(course)
for neighbor in adj[course]:
in_degree[neighbor] -= 1 # 한 개 선행 조건 완료
if in_degree[neighbor] == 0:
q.append(neighbor)
# 4. 전체 수업 수와 결과 길이가 다르면 → 싸이클 존재
return res if len(res) == numCourses else []🧠 예시
numCourses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]- 초기 in-degree: [0, 1, 1, 2]
- 큐 시작: [0]
- 순차적으로:
0 → 1, 2 → 3
→ 결과: [0, 1, 2, 3] 또는 [0, 2, 1, 3] 등 가능
📊 시간/공간 복잡도
| 항목 | 복잡도 |
| 시간 | O(V + E) = O(numCourses + prerequisites.length) |
| 공간 | O(V + E) |
✅ 언제 DFS, 언제 Kahn's?
| 방식 | 특징 |
| DFS (post-order) | 직관적이고 재귀 기반, 사이클 탐지 쉽게 포함 가능 |
| BFS (Kahn’s) | 코드가 깔끔하고, 사이클 확인이 쉬움 (큐 비고 길이 비교) |
⏱️ 비교표
| 항목 | DFS 위상 정렬 | BFS(Kahn’s Algorithm) |
| 시간 복잡도 | O(V + E) | O(V + E) |
| 공간 복잡도 | O(V + E) | O(V + E) |
| 사이클 탐지 | visiting 집합으로 명시적으로 체크 | res 길이 < V로 판단 |
| 장점 | 재귀 기반, 구조 이해 쉬움 | 구현이 깔끔하고 큐로 처리 |
추가로 이 문제에서 recursion depth가 최대 2000개까지 갈 수 있어서,
인터뷰나 실무에서는 BFS 방식이 조금 더 안전할 수도 있어요 (스택 오버플로 방지 차원에서).
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# 전체 강의듣는 순서 리턴
# prerequisites [a, b]: b->a
if numCourses == 1:
return [0]
adj = {}
for i in range(numCourses):
adj[i] = []
for a, b in prerequisites:
adj[b].append(a)
res = []
visited = set()
visiting = set()
def isCycle(n):
if n in visited:
return False
if n in visiting:
return True
visiting.add(n)
for nei in adj[n]:
if isCycle(nei): # is cycle:
return True
visiting.remove(n)
res.append(n)
visited.add(n)
return False
for i in range(numCourses):
if i not in visited:
if isCycle(i): # 싸이클 있으면 , 전체 수강 못함
return []
return res[::-1] # 위상정렬..뒤집어서 리턴