파이썬 알고리즘 인터뷰 - 39. 코스 스케줄

 

<--- 리트코드 207. Course Schedule --->

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

 

입력

2, [[1,0]]

출력

true

 

입력

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

출력

false

 

 

# 풀이

1. DFS로 순환 구조 판별

import collections
 
def can_finish(num_courses, prerequisites):
  graph = collections.defaultdict(list)
 
  for x, y in prerequisites:
    graph[x].append(y)
 
  traced = set()
 
  def dfs(i):
    if i in traced:
      return False
 
    traced.add(i)
    for y in graph[i]:
      if not dfs(y):
        return False
 
    traced.remove(i)
 
    return True
 
  for x in list(graph):
    if not dfs(x):
      return False
 
  return True
 
num_courses = 2
prerequisites = [[1,0]]
print(can_finish(num_courses, prerequisites))

 

2. 가지치기를 이용한 최적화

import collections
 
def can_finish(num_courses, prerequisites):
  graph = collections.defaultdict(list)
 
  for x, y in prerequisites:
    graph[x].append(y)
 
  traced = set()
  visited = set()
 
  def dfs(i):
    if i in traced:
      return False
    if i in visited:
      return True
 
    traced.add(i)
    for y in graph[i]:
      if not dfs(y):
        return False
 
    traced.remove(i)
    visited.add(i)
 
    return True
 
  for x in list(graph):
    if not dfs(x):
      return False
 
  return True
 
num_courses = 2
prerequisites = [[1,0]]
print(can_finish(num_courses, prerequisites))