207. Course Schedule

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

Course Schedule - LeetCode

Solution

from queue import Queue

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        q = Queue()
        a2b = {} # a : 조건이 필요한 수업
        b2a = {} # b : 조건
        for a, b in prerequisites:
            if a==b:
                return False
            if a2b.get(a):
                a2b[a].append(b)
            else:
                a2b[a] = [b]
            if b2a.get(b):            
                b2a[b].append(a)
            else:
                b2a[b] = [a]

        for i in range(numCourses):
            if not a2b.get(i):
                q.put(i)

        while(not q.empty() and a2b):
            i = q.get()
            if not b2a.get(i):
                continue
            for j in b2a[i]:
                a2b[j].remove(i)
                if len(a2b[j]) == 0:
                    q.put(j)
                    del a2b[j]
        
        if len(a2b):
            return False
        return True

• 큐와 두 개의 딕셔너리를 생성한다.
• prerequisites를 보면서, 각 수업마다 필요한 조건과, 각 조건마다 딸려있는 수업들을 저장한다.
• 조건 없는 수업들을 큐에 넣는다.
• 큐에서 하나씩 꺼내가며, 그것을 조건으로 가지고 있는 수업들의 조건들을 하나씩 만족시켜간다.
• 그 때 수업의 모든 조건이 만족하면 딕셔너리에서 없애고 큐에 넣는다.
• 큐에서 꺼낼 수업이 없거나, 모든 조건을 만족했을 때 while문을 종료한다.
• 만족해야할 조건이 더 남았다면 False를 반환한다.

Another

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]
        for x, y in prerequisites:
            graph[x].append(y)
            
        visited = [0 for _ in range(numCourses)]

        for i in range(numCourses):
            if not self.dfs(graph, visited, i):
                return False
        return True
    
    def dfs(self, graph, visited, i):
        if visited[i] == -1:
            return False
        if visited[i] == 1:
            return True
            
        visited[i] = -1

        for j in graph[i]:
            if not self.dfs(graph, visited, j):
                return False

        visited[i] = 1
        return True

• cycle이 있으면 모든 수업을 들을 수 없으므로, False를 반환해야 한다.
• 방향은 상관 없이 cycle만 없으면 된다.
• dfs로 들린 i에 해당한 visited를 -1을 넣어서 방문했음을 나타낸다.
• 그 아래 노드들로 계속 방문한다.
• 연결된 그래프를 따라 가다가 -1이 나오면 이미 들린 곳이므로 False를 반환한다.
• 하위 노드를 다 들렸을 때 False를 한번도 발견하지 않은 노드는 1을 넣는다.
• 연결된 그래프를 따라 가다가 1을 만나면, 아래는 다 괜찮다는 뜻이므로 True를 반환한다.

 

• 의문이 드는 점은 아래의 상황이다. 이런 상황에서는 모든 수업을 수강할 수 있으므로, -1을 만나더라도 예외처리해야하는 것이 아닐까? 이런 상황은 예시에 나오지 않았나보다.

queue

from queue import Queue

q = Queue()

q.put(1)
print(q.qsize()) 		# 1
a = q.get() 			# a = 1
if q.empty():
	print('is empty') 	# is empty
    
'''
q.put()
q.qsize()
q.get()
q.empty()
'''

python에서 queue의 기본 사용법이다.