[LeetCode] 207. Course Schedule

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

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. 문제 설명

[ai, bi] = ai 과목을 듣기 위해선 bi 과목을 먼저 들어야한다.

주어진 prerequisites 목록을 이용하여 모든 과목을 다 들을 수 있는지 판단하라.

 

2. 해결 방법

노드들 간의 방향성이 있는 그래프를 그린다.

순환되는 구간이 있는지 판단한다.

 

3. 주의 사항

- [5,5] 같이 자기 자신이 선행과목인 경우는 항상 실패

- 그래프 탐색이기 때문에 checked를 이용하여 중복 탐색 방지 가능

 

4. 나의 풀이

class Solution {
    
    HashMap<Integer, Node> hashMap = new HashMap<Integer, Node>();
    HashMap<Integer, Boolean> checked = new HashMap<Integer, Boolean>();


    public boolean canFinish(int numCourses, int[][] prerequisites) {
        for(int i = 0; i< prerequisites.length;i++) {
            if(prerequisites[i][0] == prerequisites[i][1]) {
                return false;
            }
            Node parent = getOrCreateNode(prerequisites[i][1]);
            Node child = getOrCreateNode(prerequisites[i][0]);
            parent.addChild(child);
        }

        for(Integer key : hashMap.keySet()) {
            HashMap<Integer, Boolean> history = new HashMap<Integer, Boolean>();
            history.put(hashMap.get(key).value, true);
            if (checked.containsKey(key)) {
                continue;
            }

            checked.put(key, true);
            if(!canFinish(hashMap.get(key), history)) {
                return false;
            }
        }
        return true;
    }

    public boolean canFinish(Node parent, HashMap<Integer, Boolean> history) {
        for(Node child : parent.children) {
            if (checked.containsKey(child.value)) {
                continue;
            }
            checked.put(child.value, true);

            for(Node childchild : child.children) {
                if(history.containsKey(childchild.value)) {
                    return false;
                }
            }
            history.put(child.value, true);
            if (!canFinish(child, history)) {
                return false;
            }
            history.remove(child.value);
        }
        return true;
    }

    public Node getOrCreateNode(int value) {
        if (hashMap.containsKey(value)) {
            return hashMap.get(value);
        } else {
            Node node = new Node(value);
            hashMap.put(value, node);
            return node;
        }
    }
}

class Node {
    int value;
    List<Node> children;

    public Node(int value) {
        this.value = value;
        this.children = new ArrayList<Node>();
    }

    public void addChild(Node child) {
        this.children.add(child);
    }
}

 

5. 고수의 풀이

 

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] dc = new int[numCourses];
        for (int[] pre : prerequisites) {
            dc[pre[1]]++;
        }
        boolean[] v = new boolean[prerequisites.length];
        boolean p = true;
        while(p) {
            p = false;
            for (int i = 0; i < prerequisites.length; i++) {
                if(!v[i] && dc[prerequisites[i][0]] == 0) {
                    v[i] = true;
                    p = true;
                    dc[prerequisites[i][1]]--;
                }
            }
        }
        for(int c : dc)
            if( c != 0) return false;
        return true;
    }
}