Leetcode 207. Course Schedule 풀이 (Topological Sorting, BFS, DFS)

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

Course Schedule - LeetCode

 

---

 

이 문제를  풀기 위해서는 Topological Sorting에 대한 이해가 필요하기 때문에 정리해보려합니다

 

√ Topological Sorting (위상정렬) 이란?

Directed Acyclic Graph (방향성비순환그래프, DAG)의 꼭지점들이 선형적으로 정렬된 것을 의미합니다

DAG이름이 어렵지만 말 그대로 순환형태의 관계가 아닌 그래프를 일자로 쭉 나열한다! 고 보면 될 것 같습니다

대학교 선수과목처럼 v가 실행되기 위해서는 u가 선행되어야 하는 방식인데요 

 

Source: https://guides.codepath.com/compsci/Topological-Sort

 

여기서 기본 개념은

하나의 꼭지점에서 다른 꼭지점으로 나가는 화살표를 = > Out-degree

반대로 하나의 꼭지점을 가르키는 들어오는 화살표를 = > In-degree로 부릅니다

 

 

이러한 정렬을 실행하기 위해서는 크게 deque를 이용한 BFS, 재귀를 사용하는 DFS 2가지 방법으로 나뉘어지는데요

 

코드를 보면서 분석해보겠습니다 :))

 

---

√  BFS _ In-degree visited 방법

아래 2가지 방식은 원리는 같지만 서술한 방식이 다른 풀이입니다

 

1.  in-degree와 이웃된 node를 담는 객체를 만듭니다

(여기서 defaultdict를 사용한 이유는 default로 int의 경우 0, list 는 [] 빈 리스트를 생성해주기 위함입니다)

 

2. prerequisites에서 (u,v)의 첫 선행항목 u (in-degree)를 앞서 생선한 default dict에 배정해줍니다

 

3. 아래의 starts는 indegree가 없는 = 선행되는 항목이 없는 = 시작점으로 작용할 수 있는 노드를 지정해주고

    노드의 방문 여부를 체크하는 비어 있는 set 혹은 deque 를 만듭니다

 

4. 시작점부터 시작!

   시작점을 뽑아서 방문했다는 visited에 넣습니다

 

5. 이제 시작점에서 인근한 이웃리스트에 담아 뒀던 노드를 꺼내서  in-degree에서 1을 빼서 0으로 만듭니다

 

6. 0이 된 이웃들의 in-degree를 visited에 추가합니다

 

7. start가 없을 때까지 반복해서 선행관계가 끝났을 때 알고리즘을 마칩니다

 

▷ Stack 이용

from collections import defaultdict

def canFinish1(self,numCourses,prerequisites):
	indegree = defaultdict(int)
    	adj_list = defaultdict(list)
    
    for pre in prerequisites:
   	indgree[pre[0]] += 1
    	adj_list[pre[1]].append(pre[0])
    
    starts, visited = [i for i in range(numCourses) if not indegree[i]], set()
    
    while starts:
    	node = starts.pop()
        if node in visited: continue
        visited.add(node)
        
        for neigh in adj_list[node]:
        	indegree[neigh] -= 1
            	if not indegree[neigh]:
            		starts.append(neigh)
    return len(visited) == numCourses

 

▷Deque 이용

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        
        base_dict = collections.defaultdict(set)
        adv_dict = collections.defaultdict(set) 
        
        for a, b in prerequisites:
            base_dict[a].add(b)
            adv_dict[b].add(a)
        
        learning = collections.deque()  #이전 풀이와 deque를 사용한 차이
        for course in range(numCourses):
            if not base_dict[course]:
                learning.append(course)
        
        learned_count = 0
        while learning:
            base = learning.popleft()
            learned_count += 1
            
            for adv in adv_dict[base]:
                base_dict[adv].remove(base)
                if not base_dict[adv]:
                    learning.append(adv)
        
        return learned_count == numCourses

개인적으로 이 방법이 좀 더 이해가 잘되고 편리한 것 같습니다

---

 

DFS _ 재귀 이용방법

def canFinish(self, numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    visit = [0 for _ in range(numCourses)]
    
    for x, y in prerequisites:
        graph[x].append(y)
        
    def dfs(i):
        if visit[i] == -1:
            return False
        if visit[i] == 1:
            return True
        visit[i] = -1
        for j in graph[i]:
            if not dfs(j):
                return False
        visit[i] = 1
        return True
        
    for i in xrange(numCourses):
        if not dfs(i):
            return False
    return True
    
    # NOT VISITED 0 , VISITING -1, ALREADY VISITED 1