<aside> 👨🏿‍💻 코스 스케줄 링크

</aside>

문제 정리

<aside> 👨🏿‍💻 코스 개수 numCourses가 주어진다.

전제 조건인 prerequisites가 주어진다.

전제 조건은 prerequisites = [a, b] 형태이며 a를 끝내기 위해서 b를 완료해야한다.

전제 조건을 완료할 수 있는지 출력하자.

</aside>

예시로 정리

<aside> 👨🏿‍💻 사실 이문제를 이해하는데 상당히 오래 걸렸다. 예시로 알아보자.

</aside>

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
# 1을 완료하기 위해 0을 끝내야하기 때문에 True가 정답

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
# 1을 완료하기 위해 0을 끝내야하고 0을 완료하기 위해 1을 끝내야한다. 따라서 False가 정답.

<aside> 👨🏿‍💻 예시로 봐도 무슨 말인지 모르겠다. 책을 보자

이 문제는 주어진 전제 조건을 그래프로 그렸을 때 순환 구조인지 판별하는 문제이다.

순환 구조라면 빙글빙글 돌아서 처리할 수 없게 되어 False가 처리된다.

</aside>

풀이의 접근 방법

<aside> 👨🏿‍💻 (1) 페어들의 목록인 prerequisites를 풀어서 그래프로 표현한다.

(2) 순환 구조 알고리즘을 만들어 판별한다.

</aside>

코드 진행

<aside> 👨🏿‍💻 먼저 그래프로 표현하자.

</aside>

def canFinish(self, numCourses, prerequisites):
        graph = collections.defaultdict(list)

        # 그래프 구성
        for x, y in prerequisites:
            graph[x].append(y)

<aside> 👨🏿‍💻 이미 방문했던 노드를 traced에 저장한다. 중복 방문하게 된다면 순환 구조로 판별할 수 있기 때문에 종료할 수 있다. 중복값을 갖지 않아 set으로 저장한다.

</aside>

traced = set()