[Leetcode] 207. Course Schedule

[yenzip]

문제 링크

[ASak1104]

207. Course Schedule

• 언어 : Kotlin
• 코드 : 깃허브
• 성능 : Time: 194 ms (74.76%), Space: 42.4 MB (38.35%)

Kotlin 풀이

```kt class Solution { val edges: Array> = Array(2000) { arrayListOf() } val inDegrees: IntArray = IntArray(2000) var n: Int = 0 fun canFinish(numCourses: Int, prerequisites: Array): Boolean { n = numCourses for ((u, v) in prerequisites) { edges[u] += v inDegrees[v]++ } return isCompletableCourses() } fun isCompletableCourses(): Boolean { val deque: ArrayDeque = ArrayDeque(n) var completableCourse: Int = 0 for (u in 0 until n) { if (inDegrees[u] == 0) { deque += u } } while (deque.isNotEmpty()) { val u = deque.removeFirst() for (v in edges[u]) { if (--inDegrees[v] == 0) { deque += v } } completableCourse++ } return completableCourse == n } } ```

코멘트

• 처음 접했을 때 풀기 힘든 알고리즘인 Topological Sort (위상 정렬) 문제네요
• 보통 2가지 방식으로 문제를 푸는 편입니다!
  • Queue + InDegree
  • Stack or Dfs
• 저는 대부분 Queue로 푸는 편이에요!

[shoeone96]

207. Course Schedule

• 언어 : java
• 성능 :

코드 풀이

```java class Solution { public boolean dfs(Map> finishToTakeMap, Integer finish, List takes, List taken) { if (takes.contains(finish)) return false; if (taken.contains(finish)) return true; if (finishToTakeMap.containsKey(finish)) { takes.add(finish); for (Integer take : finishToTakeMap.get(finish)) { if (!dfs(finishToTakeMap, take, takes, taken)) return false; } takes.remove(finish); taken.add(finish); } return true; } public boolean canFinish(int numCourses, int[][] prerequisites) { Map> finishToTakeMap = new HashMap<>(); for (int[] pre : prerequisites) { finishToTakeMap.putIfAbsent(pre[0], new ArrayList<>()); finishToTakeMap.get(pre[0]).add(pre[1]); } List takes = new ArrayList<>(); List taken = new ArrayList<>(); for (Integer finish : finishToTakeMap.keySet()) { if (!dfs(finishToTakeMap, finish, takes, taken)) return false; } return true; } } ```

코멘트

• 두 번째 책 코드로 풀었습니다.

[yenzip]

207. Course Schedule

• 언어: C++
• 성능: Time: 12ms (94.87%), Memory: 14.97MB (38.74%)

코드 풀이

```C++ class Solution { public: vector> graph; int status[2001]; // {0 : notVisited, 1: visiting, 2: visited } bool dfs(int now) { // isCycle(순환 여부 확인 -> true = cycle) status[now] = 1; // 현재 노드를 notVisited -> visiting(방문중)으로 변경 for(int next : graph[now]) { // 인접 노드 탐색 if(status[next] == 1 || (status[next]== 0 && dfs(next))) { // 1. status[next] == 1 : 방문중인 노드 다시 방문 == 순환, 2. status[next] == 0 && dfs(next) 방문중이지 않은 노드지만, 해당 노드에서 순환이 발생한 경우 return true; } } status[now] = 2; // 모든 인접 노드에 대한 탐색이 완료되면 visited(방문완료)로 변경 return false; // 모든 노드를 탐색할 수 있고, 순환이 없다면 false 반환 } bool canFinish(int numCourses, vector>& prerequisites) { graph.resize(numCourses); for (vector prerequisite : prerequisites) { // 그래프 만들기 ex) [1, 0] : 0 -> 1 graph[prerequisite[1]].push_back(prerequisite[0]); } for (int i = 0; i < numCourses; i++) { if (status[i] == 0 && dfs(i)) { // Cycle 발견 -> false return false; } } return true; } }; ```

코멘트

• 주어진 그래프에서 모든 노드를 탐색하면서 순환하지 않은 그래프인지 확인하는 문제입니다.
• 기존처럼 visited(방문 여부)를 0과 1로 두고 풀었는데, 시간초과가 나서 GPT의 도움으로 해결했습니다..!
• 근데 문제 너무 어려워요 😢

[uijin-j]

207. Course Schedule

• Language : Java
• 성능 🌟 시간: 4 ms, 메모리: 44.75MB 🌟

코드 풀이

```java class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List[] canTake = new ArrayList[numCourses]; int[] leftCourses = new int[numCourses]; for (int i = 0; i < numCourses; i++) { canTake[i] = new ArrayList<>(); } for (int[] prerequisite : prerequisites) { canTake[prerequisite[1]].add(prerequisite[0]); leftCourses[prerequisite[0]]++; } Queue queue = new LinkedList<>(); for (int i = 0; i < numCourses; i++) { if (leftCourses[i] == 0) { queue.add(i); } } int count = 0; while (!queue.isEmpty()) { int current = queue.poll(); count++; for (int course : canTake[current]) { leftCourses[course]--; if (leftCourses[course] == 0) { queue.add(course); } } } return count == numCourses; } } ```

코멘트

• 처음에는 dfs로 모든 경우를 구한 뒤, 조건에 맞는지 check를 했는데요! 이렇게 풀면 시간초과가 나더라구요ㅠㅜ 그래서 GPT에 힘을 빌렸습니다.. 언제 bfs를 쓰고 언제 dfs를 써야할지 감이 안잡히네요ㅠ