[Leetcode 15/100] Course Schedule - Medium

문제 풀이 방식

Graph에서 Cycle을 찾는 재귀 함수 구현

주의할 점

처음에 findCycle() 함수 설계를 잘못했는데 너무 오래 매달렸다.

초기 설계를 잘하고 아니다 싶으면 바로 포기한 후에 새로운 방식으로 구현하는 것도 하나의 방법일 것 같다.

또한, 그래프에서 Cycle을 찾는 구현 방법을 정확하게 숙지하는 것이 필요할 것 같다.

위상정렬로도 풀 수 있는 문제인데 학습하자

소스코드

class Solution {
        boolean[] visitied;
        List<List<Integer>> graph = new LinkedList();
        public boolean canFinish(int numCourses, int[][] prerequisites) {

            visitied = new boolean[numCourses];

            getGraph(numCourses, prerequisites);

            for(int i=0; i<numCourses; i++){
                if(!findCycle(i))
                    return false;
            }

            return true;
        }

        private boolean findCycle(int cur) {
            if(visitied[cur])
                return false;

            visitied[cur] = true;

            List<Integer> preList = graph.get(cur);

            for(int i=0; i<preList.size(); i++){
                if(!findCycle(preList.get(i))){
                    return false;
                }
            }
            visitied[cur] = false;
            return true;
        }


        private void getGraph(int numCourses, int[][] prerequisites) {

            for(int i=0; i<numCourses; i++){
                graph.add(new LinkedList<>());
            }

            for(int i=0; i<prerequisites.length; i++){
                // [0,1] 1 -> 0, 현재 코스를 듣기 위한 선수 과목 리스트를 만듬.
                int preCourse = prerequisites[i][1];
                int course = prerequisites[i][0];
                List<Integer> list = graph.get(course);
                list.add(preCourse);
            }

        }
    }