문제 소개
총 n개의 강좌가 있으며, 각 강좌는 0부터 n-1까지 번호가 매겨져 있다고 가정해 봅시다. 일부 강좌는 선수 과목(먼저 이수해야 하는 과목)이 존재할 수 있습니다. 전체 강좌 수와 선수 과목 쌍의 목록이 주어졌을 때, 모든 강좌를 이수하기 위한 수강 순서를 찾아야 합니다.
정답이 되는 순서는 여러 개 존재할 수 있으며, 이 경우 그중 하나만 반환하면 됩니다. 만약 모든 강좌를 이수하는 것이 불가능하다면 빈 배열을 반환해야 합니다.
예시
입력이 numCourses = 2, prerequisites = [[1, 0]]이라면 결과는 [0, 1]입니다. 총 2개의 강좌가 있고, 1번 강좌를 수강하려면 먼저 0번 강좌를 이수해야 하므로 올바른 수강 순서는 [0, 1]이 됩니다.
풀이 접근 방법
이 문제는 DFS(깊이 우선 탐색) 기반의 위상 정렬(Topological Sort)로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 메인 메서드는
numCourses와prerequisites를 입력받습니다. in_degree배열을 정의하여 모든 노드의 진입 차수를 저장하고, 그래프의 인접 리스트(adj)를 생성합니다.visited배열을numCourses크기만큼 0으로 초기화합니다. (0: 미방문, -1: 탐색 중, 1: 탐색 완료)- 빈 스택을 하나 정의합니다.
- 0부터 numCourses-1까지 반복하면서, 아직 방문하지 않은 노드에 대해 DFS를 수행합니다.
- 이때 DFS가 실패하면(사이클이 발견되면) 빈 리스트를 반환합니다.
- 모든 노드의 탐색이 성공적으로 끝나면, 스택의 요소를 역순으로 반환합니다.
DFS 함수의 동작 원리
visited[node] == -1: 현재 탐색 경로에서 다시 만난 노드이므로 사이클이 존재 → False 반환visited[node] == 1: 이미 처리가 완료된 노드 → True 반환- 현재 노드를 -1로 표시한 뒤, 인접한 모든 노드를 재귀적으로 탐색합니다.
- 모든 자식 노드의 탐색이 끝나면 상태를 1로 변경하고, 해당 노드를 스택에 추가한 후 True를 반환합니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def findOrder(self, numCourses, prerequisites):
in_degree,adj=self.create_adj(numCourses,prerequisites)
visited = [0 for i in range(numCourses)]
stack = []
for i in range(numCourses):
if not visited[i] and not self.dfs(i,visited,stack,adj):
return []
return stack[::-1]
def create_adj(self,n,graph):
adj = {}
in_degree= [0 for i in range(n)]
for i in graph:
in_degree[i[0]]+=1
if i[1] in adj:
adj[i[1]].append(i[0])
else:
adj[i[1]] = [i[0]]
return in_degree,adj
def dfs(self, node, visited,stack,adj):
if visited[node] == -1:
return False
if visited[node] == 1:
return True
visited[node] = -1
if node in adj:
for i in adj[node]:
if not self.dfs(i,visited,stack,adj):
return False
visited[node]=1
stack.append(node)
return True
ob = Solution()
print(ob.findOrder(2, [[1,0]]))입력
2 [[1,0]]
출력
[0,1]
복잡도 분석
각 노드와 간선을 한 번씩만 방문하므로 시간 복잡도는 O(V + E)입니다. 여기서 V는 강좌(노드)의 수, E는 선수 과목 관계(간선)의 수입니다. 공간 복잡도 역시 방문 배열, 인접 리스트, 스택 저장에 O(V + E)가 필요합니다.