Course Schedule (Graph)

하루히즘·2021년 4월 29일
0

LeetCode

목록 보기
10/17

설명

LeetCode의 Course Schedule 문제다.

0부터 N-1까지 식별자로 구별되는 N개의 수강 과목이 주어진다. 그리고 선수과목을 나타낸 리스트가 주어진다. 각 수강 순서는 [A, B] 형태며 A를 수강하려면 선수 과목 B를 먼저 수강해야 한다는 것을 의미한다. 이때 모든 과목을 수강할 수 있는지를 판단하는 것이 문제의 목적이다.

예를 들어 2개의 수강 과목이 있으며 수강 순서가 [1, 0]처럼 주어질 때 모든 과목을 수강할 수 있다. 왜냐면 1번 과목을 수강하려면 0번 과목을 수강해야 하는데 0번 과목은 선수 과목이 없기 때문에 0번, 1번 순서로 수강할 수 있기 때문이다.

만약 수강 순서가 [1, 0], [0, 1]처럼 주어진다면 수강할 수 없는 과목이 생긴다. 왜냐면 1번 과목을 들으려면 0번 과목을 들어야 하는데 0번 과목을 들으려면 1번 과목을 들어야 하기 때문이다. 즉 서로 꼬리를 물게 된다.

풀이

학교 커리큘럼에서 많이 본 구조지만 이번 문제는 선수 과목이 후수 과목이 꼬리를 무는 형태인지, 즉 그래프가 순환 구조인지 판단하는 것이 핵심이다.

헷갈릴 수 있는 점은 모든 과목이 선수 과목이 필요한 게 아니기 때문에 선수 과목이 지정된 과목들에 대해서만 탐색하면 된다. 그래프의 연결 관계는 사전(dict)과 리스트(list) 자료형을 이용하여 구축할 수 있다.

그리고 모든 과목들, 정확히는 선수 과목이 있는 과목들에 대하여 재귀적으로 DFS 탐색하여 수강 가능한 과목인지 파악할 수 있다.
예를 들어 위의 그림처럼 과목 1의 선수 과목인 과목 A, B, C를 탐색한다고 하자. 다시 재귀적으로 과목 A, B, C의 선수 과목들도 파악해야 한다.

먼저 과목 A의 선수 과목인 과목 B를 보면 선수 과목 정보에서 과목 B는 선수 과목으로 과목 A를 요구한다는 것을 알 수 있다. 이러면 과목 A를 수강하기 위해 과목 B를 수강해야 하고 과목 B를 수강하려면 과목 A를 수강해야 하는 꼬리물기 상황이 펼쳐진다. 즉 순환 그래프인 것이다.

이 경우 모든 과목을 정상적으로 수강할 수 없다고 판단하면 된다. 위의 순환을 파악하려면 지금까지 탐색한 노드(과목)에 과목 A를 추가해두고 이 과목의 선수 과목을 파악하는 과정에서 과목 A를 요구하는 경우가 있는지로 판단할 수 있을 것이다.

DFS(시간 초과)

DFS를 이용한 방법은 위에서 생각한 풀이를 그대로 구현한 것이다.

import collections


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 그래프 구축.
        requirements = collections.defaultdict(list)
        for course, prerequisite in prerequisites:
            requirements[course].append(prerequisite)
        
        # 현재 선수 과목을 파악중인 과목 리스트.
        alreadyTaken = set()
        # 선수 과목 탐색.
        def checkValidPrerequisites(currentCourse):
            # 만약 현재 과목이 선수 과목을 파악중인 과목이라면 False 반환.
            # 예를 들어 1번 과목의 선수 과목 2번을 파악중일 때
            # 2번 과목의 선수 과목이 1번 과목이라면 순환이 발생.
            if currentCourse in alreadyTaken:
                return False
            
            # 현재 과목도 선수 과목을 파악중인 과목에 포함.
            alreadyTaken.add(currentCourse)
            # 현재 과목의 선수 과목도 파악, 순환 여부에 따라 False 반환.
            for prerequisite in requirements[currentCourse]:
                if checkValidPrerequisites(prerequisite) == False:
                    return False
            
            # 현재 과목의 선수 과목 탐색이 끝났다면 리스트에서 현재 과목 제거.
            alreadyTaken.remove(currentCourse)
            # 현재 과목은 문제없이 수강할 수 있음.
            return True
        
        for course in range(numCourses):
            # 모든 과목마다 선수 과목 확인.
            if checkValidPrerequisites(course) == False:
                return False
            
        return True

나쁘지 않은 방법이었지만 100개의 과목과 수십 개의 선수 과목이 주어졌을 때는 시간 초과 문제가 발생했다. 왜냐면 한 수업에 대한 중복된 탐색이 발생했기 때문인데 생각해보면 한 수업이 다른 수업의 선수 과목일 때 이 수업을 문제없이 들을 수 있다고 탐색했다고 하자. 그렇다면 나중에 이 수업을 선수 과목으로 가지는 다른 수업을 탐색할 때 굳이 이 수업의 선수 과목을 다시 탐색할 필요가 없다는 것을 떠올릴 수 있다.

DFS with Pruning(84 ms)

그래서 수강에 문제가 없는 과목을 따로 저장하는 집합(safeToTake)을 이용하여 만약 선수 과목이 '문제가 없는 과목'이라면 더이상 탐색하지 않고 기존 탐색 결과를 활용하도록 구현할 수 있다.

import collections


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 그래프 구축.
        requirements = collections.defaultdict(list)
        for course, prerequisite in prerequisites:
            requirements[course].append(prerequisite)
        
        # 현재 선수 과목을 파악중인 과목 리스트.
        alreadyTaken = set()
        # 수강에 문제가 없다고 파악된 과목 리스트.
        safeToTake = set()
        # 선수 과목 탐색.
        def checkValidPrerequisites(currentCourse):
            # 만약 현재 과목이 선수 과목을 파악중인 과목이라면 False 반환.
            if currentCourse in alreadyTaken:
                return False
            # 만약 현재 과목이 수강에 문제가 없다고 파악된 과목이라면 True 반환.    
            if currentCourse in safeToTake:
                return True
            
            # 현재 과목도 선수 과목을 파악중인 과목에 포함.
            alreadyTaken.add(currentCourse)
            # 현재 과목의 선수 과목도 파악, 순환 여부에 따라 False 반환.
            for prerequisite in requirements[currentCourse]:
                if checkValidPrerequisites(prerequisite) == False:
                    return False
            
            # 현재 과목의 선수 과목 탐색이 끝났다면 리스트에서 현재 과목 제거.
            alreadyTaken.remove(currentCourse)
            # 현재 과목을 수강할 수 있다면 리스트에 추가하고 True 반환.
            safeToTake.add(currentCourse)
            return True
        
        for course in range(numCourses):
            # 모든 과목마다 선수 과목 확인.
            if checkValidPrerequisites(course) == False:
                return False
            
        return True

이 경우 84ms의 속도로 모든 테스트 케이스를 통과할 수 있었다. 단순히 몇 줄 추가한 코드지만 중복되는 탐색을 제거할 수 있는 방법이었기 때문에 효과가 확실히 나타나는 것을 알 수 있다.

참고자료

파이썬 알고리즘 인터뷰

profile
YUKI.N > READY?

0개의 댓글