[LeetCode#207] Course Schedule

❒ Description

---

제목	Course Schedule
링크	https://leetcode.com/problems/course-schedule/description/
자료구조	비선형 (그래프)
시간복잡도	위상정렬 : O(v+e)

 

이번 문제는 재귀로도 풀수 있지만, Topological Sorting 알고리즘을 사용해서도 풀수 있는 문제다.

 

 

 

❒ Solution

---

1. 재귀 구조

public boolean canFinish(int numCourses, int[][] prerequisites) {
    Map<Integer, List<Integer>> finishToTakeMap = new HashMap<>();
    for (int[] prerequisite : prerequisites) {
        finishToTakeMap.putIfAbsent(prerequisite[0], new ArrayList<>());
        finishToTakeMap.get(prerequisite[0]).add(prerequisite[1]);
    }

    List<Integer> takes = new ArrayList<>();
    List<Integer> taken = new ArrayList<>();
    for (Integer finish : finishToTakeMap.keySet()) {
        if (!dfs(finishToTakeMap, finish, takes, taken)) {
            return false;
        }
    }
    return true;
}

public boolean dfs(Map<Integer, List<Integer>> finishToTakeMap, Integer finish, List<Integer> takes, List<Integer> 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;
}

 

2. 위상 정렬

public boolean courseSchedule(int numCourses, int[][] prerequisites) {
    List<List<Integer>> courses = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        courses.add(new ArrayList<>());
    }

    int[] inDegrees = new int[numCourses];
    for (int i = 0; i < prerequisites.length; i++) {
        inDegrees[prerequisites[i][0]] ++;
        courses.get(prerequisites[i][1]).add(prerequisites[i][0]);
    }

    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegrees[i] == 0) {
            q.add(i);
        }
    }

    int count = 0;
    while (!q.isEmpty()) {
        int node = q.poll();
        count++;
        for (int val : courses.get(node)) {
            inDegrees[val]--;
            if (inDegrees[val] == 0) {
                q.add(val);
            }
        }
    }
    return count == numCourses;
}