Course Schedule

🔗 문제 링크

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

🔍 문제 설명

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where $prerequisites[i] = [ai, bi]$ indicates that you must take course bi first if you want to take course ai.

• For example, the pair $[0, 1]$, indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

⚠️ 제한사항

• $1 <= numCourses <= 10^5$

• $0 <= prerequisites.length <= 5000$

• $prerequisites[i].length == 2$

• $0 <= a_i, b_i < numCourses$

• All the pairs prerequisites[i] are unique.

---

🗝 풀이 (언어 : Java)

• 위상정렬(Topology Sort)

순서가 정해져 있는 작업을 차례대로 수행해야 할 때 그 순서를 정해주기 위해 사용하는 알고리즘입니다. 위상정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능합니다. 이것은 사이클이 발생하지 않는 방향 그래프를 의미합니다. 사이클이 발생하는 경우에는 위상정렬을 수행할 수 없습니다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Queue<Integer> queue = new LinkedList<>();
        int[] graph = new int[numCourses];
        int length = prerequisites.length;
        // 위상정렬 수행할 그래프 배열 만들기
        for (int[] prerequisite : prerequisites)
            graph[prerequisite[0]]++;
        // 배열에서 값이 0인 가장 먼저 들어야 하는 강의 찾아 큐에 넣기
        for (int i = 0; i < numCourses; i++) {
            if (graph[i] == 0)
                queue.offer(i);
        }
        // 큐로 BFS를 수행하여 순차적으로 간선을 지우며 최종적으로 모두 0이 되는지 판별
        // 싸이클이 존재하면 해당 관련 원소들이 모두 0보다 커서 큐에 진입하지 못한다 -> 그래프에서 0으로 못만듦
        while (!queue.isEmpty()) {
            // 우선순위 빠른 강의로 다음 우선순위 강의와 연결을 끊어줌 (0으로 만들기)
            int num = queue.poll();
            for (int i = 0; i < length; i++) {
                if (prerequisites[i][1] == num) {
                    graph[prerequisites[i][0]]--;
                    // 만약 0이 되면 최우선 순위 강의가 되어 다음 우선순위 강의를 찾기위해 큐에 넣음
                    if (graph[prerequisites[i][0]] == 0)
                        queue.offer(prerequisites[i][0]);
                }
            }
        }
        // 그래프에서 모두 0으로 바뀌었는지 확인 -> 위상정렬 가능
        for (int n : graph) {
            if (n != 0)
                return false;
        }
        return true;
    }
}