리트코드 207번 Course Schedule (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

from typing import List
from collections import defaultdict

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        traced = set()
        visited = set()

        pre_dict = defaultdict(list)
        for a, b in prerequisites:
            pre_dict[a].append(b)

        def dfs(x):
            if x in traced:
                return False
            if x in visited:
                return True

            traced.add(x)
            for y in pre_dict[x]:
                if not dfs(y):
                    return False
            traced.remove(x)
            visited.add(x)

            return True

        for x in range(numCourses):
            if not dfs(x):
                return False

        return True

주어진 그래프에 순환구조가 있다면 모든 course를 수강할 수 없다. 따라서 중간에 순환 구조가 있는지 확인하면 된다.

방문한 노드를 traced에 추가하고, 다음에 방문할 노드가 방문했던 노드라면 순환구조라고 판단한다. 이때, 해당 노드에서의 탐색이 끝나면 traced에서 지워야한다. 그렇지 않다면 순환이 아닌데 순환이라고 판단할 수 있다.

이후 해당 노드에서 순환구조가 발견되지 않으면 visited에 추가한다. 다른 노드를 통해 탐색을 진행하다가 visited 안에 있는 노드를 발견하면 순환구조가 없다고 판단, 추가적인 탐색을 진행하지 않고 종료한다.

Reference

파이썬 알고리즘 인터뷰 39번