[1스4코2파] # 233. LeetCode 207. Course Schedule

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (233차)
[4코1파] 2023.01.13~ (225일차)
[1스4코1파] 2023.04.12~ (136일차)
[1스4코2파] 2023.05.03 ~ (114일차)

Today :

2023.08.24 [233일차]
207. Course Schedule
https://leetcode.com/problems/course-schedule/

LeetCode 207. Course Schedule

문제 설명

수강해야 하는 총 numCourses 과정은 0에서 numCourses - 1 이고,
prerequisites[i] = [ai, bi] 는 ai 과정을 수강하려면 bi 과정을 먼저 수강해야하는 것을 나타낸다.

예를 들어, [0, 1] 은 코스 0을 수강하려면 먼저 코스 1을 수강해야 하는 것을 나타내는데, 주어진 코스를 모두 완료 할 수 있는 경우 true를 반환 아니면 false를 반환함

문제 풀이 방법

각 코스에 해당하는 순서를 담는 hash table과,
들었던 코스를 기록하는 visited를 기준으로 dfs로 탐색한다.
dfs 나가는 base 코드는, visited에 있는와 hashmap에 해당하는 코스가 있는지없는지에 대한 유무임

내 코드

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        preMap = {i:[] for i in range(numCourses)}
        for crs, pre in prerequisites:
            preMap[crs].append(pre)
            
        visitedSet = set()
        def dfs(crs):
            if crs in visitedSet:
                return
            if preMap[crs] == []:
                return True
            
            visitedSet.add(crs)
            for pre in preMap[crs]:
                if not dfs(pre):
                    return False
                
            visitedSet.remove(crs)
            preMap[crs] = []
            return True
        
        for crs in range(numCourses):
            if not dfs(crs):
                return False
            
        return True

증빙

여담

쉬운 편에 속하는 dfs 같은데... 문제 base를 아직도 잘 못짜겠단 말이지?
low iq..