[LeetCode 풀이/python] 207. Course Schedule (medium)

문제 설명: 수강해야 하는 전체 강의 수를 가리키는 변수 numCourses 가 존재하며, 각 강의는 0 에서 numCourses -1 까지의 숫자로 레이블 되어 있다. 또한 배열 prerequisites 의 각 원소 prerequisites[i] = [a_i, b_i] 는 강의 a_i 를 수강하려면 반드시 강의 b_i 를 먼저 수강해야 함을 가리킨다. 예를 들어, [0, 1] 쌍은 강의 0 을 수강하기 위해 강의 1 을 먼저 들어야 함을 가리킨다. 주어진 입력에 대해, 모든 강의를 수강하는 것이 가능하다면 True 를, 아니면 False 를 리턴하시오. 

 

(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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

• 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.)

 

 

예시 1)

입력: numCourses = 2, prerequisites = [[1,0]]  -->  출력: True

설명: 전체 수강해야 할 강의 수는 2개. 강의 1을 듣기 위해서는 0을 먼저 들어야 하며, 이는 가능함. 

 

예시 2)

입력: numCourses = 2, prerequisites = [[1,0],[0,1]]  -->  출력: False

설명: 전체 수강해야 할 강의 수는 2개. 강의 1을 듣기 위해서는 0을 먼저 들어야 하고, 강의 0을 듣기 위해서는 강의 1을 먼저 들어야 하므로  이는 불가능함.

 

제한 조건:

• 1 <= numCourses <= 105
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= a_i, b_i < numCourses
• prerequisites[i] 의 모든 쌍(pair) 는 중복이 없고 고유함(unique)

 

 

------ * ------ * ------ * ------

 

[풀이 1안]  (not a solution...!)

• 접근법
  • b_i 가 a_i 의 선행 과목일 때, 동시에 a_i 가 b_i 의 선행 과목 (b_i 가 a_i 의 후행 과목) 이기도 한 상황이라면 해당 조건은 모두 만족시킬 수 없으므로 모든 강의를 수강할 수 없게 된다!
  • 선행 -> 후행 과목 관계를 유향 그래프 (directed graph) 로 표현했을 때, 해당 그래프에 cycle 이 존재하는 경우 False, 존재하지 않는 경우 True 를 리턴하면 되므로 그래프의 cycle 을 찾는 문제라 이해할 수 있음 
    • 각 강의의 선행 과목 (in-degree) 과 후행 과목 (out-degree) 를 별도의 adjacency list 에 저장한 뒤, 특정 강의의 선행 과목 리스트와 후행 과목 리스트에 동시에 존재하는 강의가 있는 경우 False...!
    • 우선 prerequisites 을 통해 직접적으로 주어진 관계들로 adjacency list 를 만든 뒤, 3단 논법(...) 을 이용해서 b 가 a 의 선행 과목이고, c 가 b 의 선행 과목이면 c 가 a 의 선행 과목이 되어야 하므로 이렇게 간접적으로 드러나는 관계를 카운트 하기 위해 adjacency list 를 업데이트 하는 step 을 추가
    • (하지만 cycle 을 찾는 방법이 틀렸다... ^^!)

 

• 코드 구현

from collections import defaultdict
def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    pre, post = defaultdict(set), defaultdict(set)
    
    # build adjacency list
    for req in prerequisites:
        pre[req[0]].add(req[1])
        post[req[1]].add(req[0])
    #print(pre, post)
        
    # update
    for p in range(numCourses):
        for c1 in pre[p]:
            pre[p] = pre[p].union(pre[c1])
        for c2 in post[p]:
            post[p] = post[p].union(post[c2])
        print(pre, post)       
    
    # check cycle
    for c in range(numCourses):
        if pre[c].intersection(post[c]):
            return False
    return True   
    

 

• 결과
  • 시간 복잡도 O(n^2)... TimeLimitExceedError 가 떠서 통과는 못 한 코드...

 

 

[풀이 2안]  (w/ solution peeping)

• 접근법
  • 데이터를 선행 -> 후행 관계를 나타내는 directed graph 형태로 표현한 뒤, 각 강의에 대해 순회하며 cycle 이 존재하는지 별도 정의한 hasCycle() 함수를 이용하여 체크
  • 각 노드의 방문 상태를 저장하는 배열 visited 에 대해, 각 노드의 상태를 기본적으로 아직 방문하지 않음 = 0 / 이전에 방문 완료 = 1 / 현재 방문(탐색) 중 = -1  으로 저장
    • hasCycle() 함수를 통해 각 노드의 탐색을 시작하면 미방문 0 에서 방문 중 -1 으로 설정
    • 해당 노드의 이웃 노드 (후행 과목) 를 방문하는 과정에서 동시에 방문 중 (-1) 인 노드와 마주치면 cycle 이 존재하는 것이므로 True (cycle 존재) 를 리턴
    • 중간에 cycle 을 발견하지 못했으면 최종적으로 방문 완료 (1) 설정하고 False (cycle 없음) 를 리턴

 

• 코드 구현

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = build_adjacency(numCourses, prerequisites)
    visited = [ 0 for _ in range(numCourses) ]

    def hasCycle(node):
        if visited[node] == 1:
            return False
        elif visited[node] == -1:
            return True
            
        visited[node] = -1
        for adj in graph[node]:
            if hasCycle(adj):
                return True
        visited[node] = 1
            
        return False
            
    for n in range(numCourses):
        if hasCycle(n):
            return False
            
    return True       
        
        
def build_adjacency(numCourses, prereq):
    graph = [ set([]) for _ in range(numCourses) ]
    for pr in prereq:
        graph[pr[1]].add(pr[0]) 
    return graph
    

 

• 결과
  • 큰 틀에서 각 노드(강의) 에 대해서 recursively 탐색하는 DFS 알고리즘 구조...!
  • Discussion 을 보니 stack 을 사용해서 이전 방문 노드들을 저장하는 방식도 있었음...!
  • BFS 알고리즘을 써서 Topological Sort 를 하는 문제로 풀 수도 있었으나 Topological Sort 에 대해 아직 이해가 부족해서 다음에 리뷰해야 할 듯...!