[LeetCode] 207. Course Schedule (Java)

문제

 

https://leetcode.com/problems/course-schedule/

Course Schedule - LeetCode

 

풀이

 

난이도: Medium 

 

선수 과목은 방향 그래프로 나타낼 수 있다.

문제에 주어지는 것은 방향 그래프의 edge이므로 선수 과목인 b에서 a로의 간선을 저장해주는 것으로 간단히 그래프를 구현할 수 있다.

 

단, 아래와 같이 0과 1 과목이 서로를 선수과목으로 가지고 있다면 두 과목 모두 수강할 수 없다.

 

따라서 수강을 처음으로 시작할 수 있는 과목은 선수 과목이 없어야 한다.

즉, 자신으로 진입하는 간선이 없어야 한다.

노드들 중에서 진입 간선이 없는 노드를 알아내기 위해 진입 차수(indegree)를 각각의 노드마다 세어주어야 한다.

 

이제 진입 차수가 0인 과목부터 BFS로 순회하며 모든 노드에 방문할 수 있다면 모든 과목을 수강할 수 있다는 의미가 된다.

단, 방문한 노드가 선수 과목을 다 방문(수강) 하지 못했다면 수강할 수 없기 때문에 선수과목의 개수(= indegree)로 이를 판단해 주어야 한다.

 

예를 들어 아래와 같은 경우 2번 과목에서 수강을 시작하지만, 인접 노드 1은 indegree가 2이기 때문에 방문을 할 수 없어 그래프를 모두 순회할 수 없게 된다.

 

 

 

코드