.leetcode(207. Course Schedule)

문제

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

문제 풀기 전

1. 순환을 찾는 문제구나.
2. 기존에는 사실 LinkedList기반아래에서 순환을 찾았는데 이렇게 배열단위의 순환은 처음이었다. 그래서 뭔가 Tores 이 방식으로 풀 수 있지 않을까 기대도 했었는데 링크드 리스트를 구지 만들어서 풀어야할까라는 생각이 들었다.

직접 푼 풀이

소요시간: 50분(22:13 ~ 11:03)

재도전하기

• 결국 못 풀었다.
• graph로 풀어보기, 기회가 되면 Tores and 요걸로 풀어보기

느낀점

1. 솔루션 하나는 방향이 비슷하게 갔다. 다만 캐쉬를 세우지 못해서 못 풀었다. 캐쉬세우니 풀렸다.
2. 2번째 방법은 graph를 이용한방법인데 처음 보는 풀이다. 이해하고 보면 결국 필수과목이 없는것부터 쳐낸다는 방식인데 기묘하다.
3. 이제 알고리즘이 조금 푸는데 시간걸리겠다는 생각이 든다. 예전에는 무조건 풀고 싶다는 생각이 들었는데 지금은 조금 버거워진 느낌이다.

솔루션 공부 후 추가로 푼 풀이

# Backtracking with memoization
class Solution {
    int max = 0;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites.length == 0) {
            return true;
        }

        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i=0; i<prerequisites.length; i++) {
            int[] current = prerequisites[i];
            if (map.containsKey(current[1])) {
                map.get(current[1]).add(current[0]);
            } else {
                Set<Integer> newSet = new HashSet<>();
                newSet.add(current[0]);
                map.put(current[1], newSet);
            }
        }


        boolean[] checked = new boolean[numCourses];
        boolean[] path = new boolean[numCourses];
        for (int i=0; i<numCourses; i++) {
            if (isCircular(map, i, checked, path)) {
                return false;
            }
        }

        return true;
    }    

    private boolean isCircular(Map<Integer, Set<Integer>> map, int index, boolean[] checked, boolean[] path) {
        if (checked[index]) {
            return false;
        }

        if (path[index]) {
            return true;
        }

        if (!map.containsKey(index)) {
            return false;
        }


        boolean ret = false;
        path[index] = true;
        for (int next: map.get(index)) {
            ret = isCircular(map, next, checked, path); 
            if (ret) {
                break;
            }
        }

        path[index] = false;
        checked[index] = true;

        return ret;
    }

}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)