Python 알고리즘 인터뷰 - 문제 39. 코스 스케쥴

leetcode 207. - https://leetcode.com/problems/course-schedule/

 

0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현 하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입렵으로 받았을 때 모든 코스가 완료 가능한지 판별하라

 

예제1

입력

2, [[1,0]]

 

출력

true

 

예제2

입력

2, [[1,0], [0,1]

 

출력

false

 

풀이

문제에 대한 이해를 하기 위해 숫자를 다음과 같이 강의 수강으로 바꿔본다.

위와 같이 python 문법을 수강하면 flask, PyTorch를 진행할 수 있다. 그러나 오른쪽처림 python문법->Flask->Django->python 문법 처럼 연결이 되면 강의 코스 설계가 논리적으로 성립하지 않는다. 문제는 이와 같은 순환참조가 있는지 여부를 판단하는 문제이다. 

 

먼저 데이터를 인접 리스트 방법으로 그래프로 변환한다.

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for p_from, p_to in prerequisites:
        graph[p_from].append(p_to)

 

그래프의 각 노드에 대해 DFS를 진행하며, 순환 구조가 있는지 여부를 확인한다.

for x in list(graph):
    if not dfs(x):
        return False

 

이제 DFS함수를 구현한다. 문제에서 각 prerequisites 노드는 unique 값을 가지고 있다고 하였으므로, set을 사용하여 방문한 노드를 기록한다.

만약 노드가 set에 존재한다면 실패로 간주하고 False를 리턴하며 백트래킹한다.

 만약 리프 노드에 도달할 경우에는 True 리턴하며 백트래킹한다. traced는 백트래킹할 때마다 해당 노드를 remove해야하는데 remove하지 않을 경우 다음 문제가 발생한다.

다음과 같이 3->1->4로 이동한 후 3으로 백트래킹한다.

이 후 3->2->4로 이동 시 '4'에서 traced에 '4'가 포함되어 있기 때문에 실패한다. 이 연결은 순환 구조가 아니므로 return False가 이뤄져서는 안된다. 

따라서 백트래킹 할 때는 traced의 값을 remove할 수 있도록한다.

traced = set()

def dfs(v):
	if v in traced:
    	return False
        
    traced.add(v)
    for w in graph[v]:
    	if not dfs(v):
        	return False
    
    traced.remove(v)
            
    return True

 

전체 코드는 다음과 같다.

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for p_from, p_to in prerequisites:
        graph[p_from].append(p_to)

    traced = set()

    def dfs(v):
        if v in traced:
            return False

        traced.add(v)
        for w in graph[v]:
            if not dfs(w):
                return False

        traced.remove(v)
        return True

    for x in list(graph):
        if not dfs(x):
            return False

    return True

 

가지치기를 통한 성능 개선

위의 코드는 leetcode 실행 시 Time Limits가 발생하며 실패한다. 이유는 for x in list(graph) 루프에서 모든 노드를 선택하여 DFS를 진행하기 때문이다. 

위와 같이 매번 노드를 방문할 때마다 DFS를 사용하여 탐색을 진행하는 것은 비효율적이다. 방문한 노드를 set을 추가하여 해당 부분은 DFS를 skip하도록 한다. 이를 가지치기라고 칭한다.

 위에서 3 노드에서는 DFS 진행 시 visited set에 순회한 노드를 추가한다. 이후 1 노드에서 순회 시 3은 이미 visited에 추가되어 있기 때문에 순회를 pass한다. 코드는 다음과 같다. 

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for p_from, p_to in prerequisites:
        graph[p_from].append(p_to)

    traced = set()
    visited = set()

    def dfs(v):
        if v in visited:
            return True

        if v in traced:
            return False

        traced.add(v)
        for w in graph[v]:
            if not dfs(w):
                return False

        visited.add(v)
        traced.remove(v)
        return True

    for x in list(graph):
        if not dfs(x):
            return False

    return True