❗️[LEET CODE] 207. Course Schedule

# Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false. Constraints: 1 <= numCourses <= 105 0 <= prerequisites.length <= 5000 prerequisites[i].length == 2 0 <= ai, bi < numCourses All the pairs prerequisites[i] are unique.

그래프가 순환구조인지 판별하는 문제

numCourses는 그냥 코스의 개수

순환 구조가 아니라면 코스 개수대로 수강 가능

 

# Solution 1 - DFS로 순환 구조 판별

Time Exceeded Error

import collections

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        # 그래프 구성
        for x, y in prerequisites:
            graph[x].append(y)

        traced = set() # 이미 방문한 노드

        def dfs(i):
            # 순환 구조이면 False
            if i in traced:
                return False

            traced.add(i)
            for y in graph[i]:
                if not dfs(y): # y가 순환구조이면 (False 이면)
                    return False
            # 탐색 종료 후 순환 노드 삭제
            traced.remove(i)

            return True

        # 순환 구조 판별
        for x in list(graph):
            if not dfs(x):
                return False

        return True

dict 형으로 그래프 구성

이미 방문한 노드는 traced에 저장 -> 다시 방문한 경우 순환구조

 

 

 

# Solution 2 - 가지치기를 이용한 최적화

import collections

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        # 그래프 구성
        for x, y in prerequisites:
            graph[x].append(y)

        traced = set()
        visited = set()

        def dfs(i):
            # 순환 구조이면 False
            if i in traced:
                return False
            # 이미 방문했던 노드이면 True
            if i in visited:
                return True

            traced.add(i)
            for y in graph[i]:
                if not dfs(y):
                    return False
            # 탐색 종료 후 순환 노드 삭제
            traced.remove(i) # 내부 모두 순환구조 아니어서 for문 빠져나오면 trace에서 삭제
            # 탐색 종료 후 방문 노드 추가
            visited.add(i)

            return True

        # 순환 구조 판별
        for x in list(graph):
            if not dfs(x):
                return False

        return True

한번 방문했던 노드는 재방문 하지 않도록 visited 변수 추가

 

for x in list(graph)로 하는 이유

for x in graph (X)

graph는 defaultdict로 선언했기 때문에 없는 키가 들어오면 디폴트 값을 생성한다

중간에 값이 변화할 수 있음

-> list(graph)로 새로운 객체 사용 (graph의 키값들)