[Leetcode 아주 상세한 문제풀이] 207. Course Schedule - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 207번 문제 Course Schedule 다.

우선 문제를 살펴보자.

 

리트코드 207번 문제 Course Schedule 링크

Course Schedule - LeetCode

Course Schedule - LeetCode

 

 

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. 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.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

 

Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

 

 

문제 설명

문제를 간략히 살펴보자. 여기서 course가 정확히 어떻게 정의되는지 모르겠지만 길이라고 생각해 보자.

문제는 길의 개수가 주어지는데 동시에 전제조건이 주어진다. 이 전제조건은 [a, b] 형태로 주어지는데 이는 a라는 길을 가기 위해서는 b라는 길을 반드시 먼저 가야 한다는 뜻이다.

예를 들어 문제 예시 1번에서 처럼 2개의 길이 주어졌다고 생각해보자. 명시는 안되어있지만 편의상 2개의 길이 '0'과 '1'이라고 생각해보자. 이때 전제조건은 [1, 0]으로 주어졌다. 즉 길 '1'을 가기 위해서는 길 '0'을 먼저 가야한다는 것이다. 2개의 길이 주어졌고 길 '0'을 먼저 간 후 길 '1'을 갈 수 있으므로 우리는 모든 길을 갈 수 있다.

하지만 문제 예시 2번을 보면 2개의 길이 주어졌는데 전제조건으로 [1, 0] 그리고 [0, 1]이 주어졌다. 이 경우는 명확히 모순되는 상황인데 길 '0'을 먼저 가고 길 '1'을 갈 경우 두번째 전제조건에 어긋한다. 반대로 길 '1'을 먼저 갈경우 첫번째 전제조건에 어긋한다. 따라서 이 경우 모든 길을 갈 수 없게 된다.

문제가 살짝 만들다 만 느낌이 있긴 하지만 어쨋든 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해 graph로 생각을 해보자.

문제 예시 2번에서 처럼 2개의 course를 노드로 표현하고 전제조건 [1, 0], [0, 1]을 연결선으로 표시해보자.

그렇다면 아래와 같이 표시할 수 있다.

1-->0-->1

이 경우 처음과 마지막에 위치한 1이 같으므로 원형 사이클을 만들 수 있다.

인풋으로 주어지는 노드와 전제조건으로 원형 사이클을 만들수 있는지 없는지가 굉장히 중요한 조건이 된다.

위 경우와 같이 연결된 노드들은 방향성을 가져야 하는데 (문제 조건에 따라) 원형 사이클을 이룬다는 것 자체가 이 방향성에 위배된다는 것이기 때문이다.

우리는 depth first search (DFS)를 이용하여 모든 노드 (=course)를 탐색할 것이다.

이때 노드는 3가지 경우의 수를 갖는다.

1) Unvisited node: 방문된 적이 없는 노드

2) Visiting node: 현재 방문하고 있는 노드

3) Visited node: 이미 방문이 된 노드

우리는 임의의 노드로부터 탐색을 시작한다.

탐색을 하는 와중에 visiting node를 방문할 경우 현재 방문하고 있는 노드와 동일하기 때문에 원형 사이클을 이룬다.

반대로 원형 사이클 없이 연결된 node를 방문한다면 그 노드들을 visited 상태로 바꾸어준다.

인풋으로 주어진 모든 노드를 탐색하고 원형 사이클이 존재하지 않음을 확인하면 (visiting node 발견이 없다면) 모든 course를 방문할 수 있다는 이야기다.

이제 코드로 한 번 살펴보자.

 

문제 풀이

Course의 개수와 전제조건을 입력받기 위한 함수를 정의해 준다. (line 1)

우리는 주어진 course의 숫자만큼 그래프를 만들어 준다. (line 3)

그리고 전제조건에 주어진 course 들을 그 그래프에 나타내준다. (line 4-5)

 

그래프에 대한 설명

이 부분에 대해 간략히 설명해 보도록 하겠다.

좀 더 명확한 이해를 위해 3개의 코스가 주어졌고 전제조건이 [1,0], [2,0], [2,1]로 주어졌다고 생각해보자.

이 경우 그래프는 [ [], [], [] ]로 3개의 코스를 나타내도록 만들어 준다.

인덱스는 각 코스를 나타내는데 편의상 순서대로 코스0, 코스1, 코스2이라고 생각해도 좋다.

이때 코스0에 해당하는 전제조건은 없다.

코스1에 해당하는 전제조건은 0이다. 전제 조건에 따라 코스0을 먼저 간 후 코스1과 코스2를 갈 수 있기 때문이다.

마지막으로 코스2에 해당하는 전제 조건은 0과 1이다. 전제 조건에 따라 코스1을 먼저 간 후 코스 2를 갈 수 있기 때문이다.

정리해조면 그래프는 [ [], [0], [0, 1]]이라고 표시된다.

즉 각 코스의 근접한 (adjacent) 노드들이 표시된다.

 

다시 코드로

다시 코드로 돌아와 보자.

우리는 모든 노드를 탐색할 예정인데 방문 노드를 표시하기 위해 변수를 하나 만들어 준다. (line 8)

이때 편의로 방문하지 않았다면 0, 방문 중이라면 1, 그리고 이미 방문 했다면 2로 표시하기로 약속하자.

맨 처음엔 어떤 노드도 방문하지 않았으므로 0으로 초기화를 시켜준다.

앞서 설명한대로 DFS 탐색을 위한 함수를 정의해 준다. (line 10)

가장 첫번째 탐색이라면 원형 사이클이 존재하는지 이미 방문한 노드인지 확인할 필요가 없다.

따라서 우선 line 11-14를 뛰어넘는다.

 

첫번째 탐색의 경우 우선 visited 변수값을 1 (=visiting)으로 업데이트 해준다. (line 16)

그리고 앞서 만든 그래프에서 해당 노드에 근접한 노드들을 탐색한다. (line 17)

근접 노드 탐색에서 원형 사이클이 탐색된다면 False를 리턴한다. (line 18-19)

이 탐색을 문제없이 마쳤다면 원형 사이클이 존재하지 않는 것이다.

따라서 해당 노드의 visited 변수값을 2 (=visited)로 업데이트 해주고 True를 리턴해준다. (line 20-21)

 

설명하지 않은 두번째 탐색의 경우를 생각해 보자.

이때는 탐색하고 있는 노드의 visited값이 1이라면 이미 방문하고 있는 (=visiting) 노드다.

따라서 방문중인 노드를 또 방문한 경우이므로 원형 사이크를 이루기 때문에 False를 리턴해준다.

만약 탐색하고 있는 노드의 visited값이 2라면이미 방문한 (=visited)  노드다.

따라서 이 경우 단순히 True를 리턴하고 탐색을 계속하면 된다.

 

우리는 인풋으로 주어진 모든 course를 for loop를 이용해 탐색한다. (line 23)

탐색하는 와중에 해당 노드의 visited 값이 0이고 (방문하지 않았고) DFS 탐색을 했는데 원형 사이클이 발견 되었다면 (nof dfs(i)) 이 경우 False를 리턴해준다. 

최종적으로 이 모든 경우에 해당하지 않는다면 원형 사이클이 존재하지 않는 것이므로 True를 리턴하고 종료해준다.

 

 

문제 풀이 코드

def canFinish(numCourses, prerequisites):
    # Create an adjacency list representation of the graph
    graph = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        graph[a].append(b)
 
    # 0 = unvisited, 1 = visiting, 2 = visited
    visited = [0] * numCourses
 
    def dfs(node):
        if visited[node] == 1:  # cycle detected
            return False
        if visited[node] == 2:  # already visited
            return True
 
        visited[node] = 1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        visited[node] = 2
        return True
 
    for i in range(numCourses):
        if visited[i] == 0 and not dfs(i):
            return False
 
    return True
 
# Test cases
print(canFinish(2, [[1,0]]))  # True
print(canFinish(2, [[1,0],[0,1]]))  # False
 

 

 

관련 문제

리트코드 128번 Longest consecutive sequence 문제 풀이 (링크)

리트코드 200번 Number of islands 문제 풀이 (링크)

 

207. Course Schedule