Course Schedule

LeetCode의 207번째 문제인 Course Schedule를 함께 풀어보도록 하겠습니다.

문제

총 numCourses 개의 과목을 수강해야 하는데 이 과목들은 0부터 numCourses - 1까지의 라벨이 붙어 있습니다. prerequisites 배열이 주어지는데, prerequisites[i] = [ai, bi]는 과목 ai를 수강하려면 먼저 과목 bi를 수강해야 한다는 것을 의미합니다.

예를 들어, [0, 1] 쌍은 과목 0을 수강하려면 먼저 과목 1을 수강해야 한다는 것을 나타냅니다.

모든 과목을 마칠 수 있는 경우 true를 반환하고, 그렇지 않은 경우 false를 반환하세요.

예제

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false

풀이 1

각 과목을 정점(vertex)로 보고, 과목 간의 관계를 간선(edge)로 보면 이 문제는 전형적인 그래프(graph) 문제로 볼 수 있는데요. 모든 과목을 수강하려면 그래프에서 순환(cycle)이 일어나면 안 됩니다. 여기서 순환이란 그래프를 순회할 때 하나의 노드를 두 번 이상 거치게 되는 상황을 의미하는데요.

그러면 어떻게 해야 주어진 그래프가 순환하는지(cyclic) 안 하는지를 알아낼 수 있을까요? 그래프를 깊이 우선 탐색하다가 동일한 노드로 다시 돌아오게 된다면 바로 순환이 있다고 판단할 수 있겠죠? 모든 노드를 들릴 때까지 동일한 노드로 다시 돌아오는 일이 없었다면 순환이 없다고 판단할 수 있을 것입니다.

간단한 예로, 다음과 같은 순환하지 않는 그래프를 순회해볼까요? A → B는 과목 A의 선수 과목이 과목 B라는 뜻입니다. 즉, 과목 A를 수강하려면 과목 B를 먼저 수강해야 한다는 거죠.

0 → 1
  ↘ ↓
3 → 2

과목 1을 수강하려면 과목 2를 수강해야하고, 과목 0을 수강하라면 과목 1과 과목 2를 수강하면 되기 때문에, 과목 2를 제일 먼저 수강하고, 그 다음 과목 1을 수강하고, 마지막으로 과목 0을 수강하면 모든 과목을 수강할 수 있습니다. 과목 3은 과목 2를 수강했다면 언제 수강해도 무방합니다.

즉, 모든 과목을 수강할 수 있는 방법은 다음과 같이 3 가지가 있습니다.

3 → 0 → 1 → 2
0 → 3 → 1 → 2
0 → 1 → 3 → 2

어떤 과목이 수강 가능한지 알아내려면, 해당 과목의 모든 선수 과목이 연쇄적으로 수강 가능해야합니다. 이를 위해서 깊이 우선 탐색으로 이 그래프를 순환해보겠습니다.

우선 과목 0을 수강하려면 선수 과목인 1과 2를 수강할 수 있어야 합니다.

❓
0 → 1
  ↘ ↓
3 → 2

둘 중에 먼저 1을 보면, 2를 먼저 수강해야합니다.

❓  ❓
0 → 1
  ↘ ↓
3 → 2

2는 선수 과목이 없어서 무조건 수강할 수 있습니다.

❓  ❓
0 → 1
  ↘ ↓
3 → 2
    ✅

따라서, 선수 과목이 2 밖에 없는 1도 수강이 가능합니다.

❓  ✅
0 → 1
  ↘ ↓
3 → 2
    ✅

0의 선수 과목인 1과 2가 모두 수강이 가능하니, 0도 수강이 가능해집니다.

✅  ✅
0 → 1
  ↘ ↓
3 → 2
    ✅

이제 확인이 필요한 과목은 3 밖에 없는데, 선수 과목인 2를 수강할 수 있으므로 3도 수강이 가능합니다.

✅  ✅
0 → 1
  ↘ ↓
3 → 2
✅  ✅

반면에, 다음과 같이 순환하는 부분이 있는 그래프는 어떨까요?

0 → 1
  ↘ ↓
3 → 2

과목 1을 수강하려면 과목 2를 수강해야하는데, 그럴려면 과목 0을 수강해야하고, 그럴려면 다시 과목 1을 수강해야합니다. 결국 과목 1에서 시작해서 다시 과목 1로 돌아오는 상황이 펼쳐지는데요. 이 경우 아무리 그래프를 순회해도 무한 루프에서 빠져나올 수 없기 때문에 모든 과목을 수강하는 것이 불가능해집니다.

❓
0 → 1
  ↖ ↓
3 → 2

❓  ❓
0 → 1
  ↖ ↓
3 → 2

💥  ❓
0 → 1
  ↖ ↓
3 → 2
    ❓

그럼 이 깊이 우선 탐색을 위한 재귀 알고리즘을 파이썬으로 구현해볼까요? 집합(Set) 자료구조를 사용하면 현재 순회 중인 노드(traversing)와 이미 순회를 마친 노드(finished)를 효과적으로 추적할 수 있습니다.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i: [] for i in range(numCourses)}
        for crs, pre in prerequisites:
            graph[crs].append(pre)

        traversing = set()
        finished = set()

        def can_finish(crs):
            if crs in traversing:
                return False
            if crs in finished:
                return True

            traversing.add(crs)
            for pre in graph[crs]:
                if not can_finish(pre):
                    return False
            traversing.remove(crs)
            finished.add(crs)
            return True

        for crs in graph:
            if not can_finish(crs):
                return False
        return True

n을 과목의 총 개수, p를 선수 관계의 수라고 했을 때, 깊이 우선 탐색을 하는 이 풀이의 시간 복잡도는 O(n+p)가 됩니다. 반면에 공간 복잡도는 세트의 메모리 사용량이 n과 비례하고 인접 리스트의 크기가 p이므로 O(n+p)이 되겠습니다.

풀이 2

위에서 작성한 파이썬 코드를 살짝 다듬어 보겠습니다.

우선 functools 내장 모듈의 @cache 데코레이터를 사용하면, finished 집합을 직접 관리해주지 않아서 편리합니다.

from functools import cache


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i: [] for i in range(numCourses)}
        for crs, pre in prerequisites:
            graph[crs].append(pre)

        traversing = set()

        @cache
        def can_finish(crs):
            if crs in traversing:
                return False

            traversing.add(crs)
            for pre in graph[crs]:
                if not can_finish(pre):
                    return False
            traversing.remove(crs)
            return True

        for crs in graph:
            if not can_finish(crs):
                return False
        return True

뿐만 아니라, all() 내장 함수를 활용하면 코드를 좀 더 줄일 수 있습니다.

from functools import cache


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i: [] for i in range(numCourses)}
        for crs, pre in prerequisites:
            graph[crs].append(pre)

        traversing = set()

        @cache
        def can_finish(crs):
            if crs in traversing:
                return False

            traversing.add(crs)
            result = all(can_finish(pre) for pre in graph[crs])
            traversing.remove(crs)
            return result

        return all(can_finish(crs) for crs in graph)

메모이제이션(memoization)을 위해서 재귀 함수에 @cache 데코레이터를 붙여준 부분을 주목하세요. 이렇게 각 노드의 수강 가능 여부를 기억해두면 해당 노드를 다시 순회할 필요가 없기 때문에 불필요한 연산을 대폭 줄일 수 있습니다.

풀이 3

해시 테이블(Hash Table)을 이용하여 각 노드가 아직 순회 이전인지, 현재 순회 진행 중인지, 아니면 순회된 것인지를 추적해보는 것은 어떨까요? 만약에 순회 중인 노드를 만난다면, 순환(cycle)이 있다는 뜻이므로 모든 과목을 수강할 수 없을 것입니다. 순회가 이미 끝난 노드를 만난다면, 해당 과목은 수강이 가능하다는 뜻입니다.

그럼 이 알고리즘을 파이썬으로 구현해볼까요? 코드가 읽기 쉽도록, 이넘을 사용하여 노드의 각 상태를 정의하겠습니다.

class Status(Enum):
    INITIAL = 1
    IN_PROGRESS = 2
    FINISHED = 3

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i: [] for i in range(numCourses)}
        for crs, pre in prerequisites:
            graph[crs].append(pre)

        statuses = {i: Status.INITIAL for i in range(numCourses)}

        def can_finish(crs):
            if statuses[crs] == Status.IN_PROGRESS:
                return False
            if statuses[crs] == Status.FINISHED:
                return True

            statuses[crs] = Status.IN_PROGRESS
            for pre in graph[crs]:
                if not can_finish(pre):
                    return False
            statuses[crs] = Status.FINISHED
            return True

        return all(can_finish(crs) for crs in graph)

이 풀이의 시간 복잡도와 공간 복잡도는 위 풀이와 다르지 않습니다. 동일한 깊이 우선 탐색을 약간 다른 스타일로 구현한 것이기 때문입니다.

마치면서

코딩 테스트에서 주어진 그래프가 순환하는지(cyclic) 비순환하는지(acyclic)를 알아내는 문제를 자주 볼 수 있는데요. 본 문제를 통해 기본기를 잘 닦아놓으셔서 같은 유형의 좀 더 어려운 문제를 풀 때 큰 도움이 되었으면 좋겠습니다.