[리트코드] 207. 코스 스케쥴 (Python)

Course Schedule - LeetCode

문제

들어야 할 총 강좌의 개수가 주어지고 그와 관련된 배열이 주어질 때 모든 과정을 이수할 수 있다면 True 아니라면 False를 출력해라.

과정

• 강좌의 개수와 전제 조건이 주어진다.
•  [a, b] 형태로 주어지는데 이는 a라는 강좌를 듣기 위해서는 b라는 강좌를 반드시 들어야 한다는 뜻이다.
• ex) [1, 0] 이 주어진다면 1 강좌를 듣기 위해서 0을 받드시 이수해야한다는 뜻이다.
  만약 [1,0] , [0,1] 이 주어진다면 1을 듣기위해서는 0을 반드시 이수해야하고 0을 듣기 위해서는 1을 반드시 이수해야 하기 때문에 모순이 발생한다. 따라서 False를 반환한다.

 

입력

numCourses = 2, prerequisites = [[1,0]]

출력

True

 

풀이

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[a].append(b)
            
        visited = [0] * numCourses

        def dfs(i):
            if visited[i] == 1:
                return False
            if visited[i] == 2:
                return True
    
            visited[i] = 1
            for n in graph[i]:
                if not dfs(n):
                    return False
            visited[i] = 2
            return True

        for i in range(numCourses):
            if visited[i] == 0 and not dfs(i):
                return False

        return True

 

한 줄씩 코드 해석해보기

graph = [[] for _ in range(numCourses)]
for a, b in prerequisites:
    graph[a].append(b)

• 그래프 리스트를 만들어주고  입력 받은 numCourses의 개수만큼 리스트를 넣어준다.
• 그 후 전제 조건에서 입력된 [a,b]의 값을 graph 인덱스 a에 b를 추가하는 식으로 넣어준다.

visited = [0] * numCourses

• 방문한 인덱스를 체크하기 위한 visited 변수에 [0]을 numCourses 개수만큼 넣어준다.
• 방문을 아직 하지 않았다면 0으로 표시한다.

def dfs(i):
    if visited[i] == 1:
        return False
    if visited[i] == 2:
        return True

• dfs함수를 정의해준다.
• 만약 입력받은 i 번째 위치의 visited리스트의 값이 1이면 False를 return한다.
• 즉, 방문 중이라면 1을 표시한다.
• 2라면 True를 return한다. 이미 방문을 했다면 2로 표시한다.

    visited[i] = 1
    for n in graph[i]:
        if not dfs(n):
            return False
    visited[i] = 2
    return True

• 첫번째 탐색의 경우 우선 visited 변수값을 1로 업데이트 해준다. (방문 중)
• 그후 그래프에서 인접한 값들을 탐색한다.
• 만약 dfs 함수를 통해 방문한 값이 1이라면 원형 사이클을 이루기 때문에 False를 return한다.
• 모든 방문이 끝나면 visited[i]의 값을 2로 바꾸어 준다. (방문 처리)
• 만약 방문한 값이 2라면 이미 방문한 값이기 때문에 True를 return 해준다.

for i in range(numCourses):
    if visited[i] == 0 and not dfs(i):
        return False

return True

• numCourses의 개수만큼 for문을 돌려준다
• 만약 탐색하는 중에 visited[i] 값이 0 이고 dfs함수에서 원형 사이클이 발견되었다면 바로 False를 return해준다.
• 위 모든 경우가 해당하지 않는다면 True를 return하고 종료한다.