[리트코드] 207. Course Schedule

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

• 해당 과목을 듣기 위해서는 반드시 먼저 들어야 할 선수과목이 있다.
  • 선수과목을 화살표로 표기해보면 방향이 있는 그래프가 만들어 진다.
• 이 문제에서는 주어진 과목을 전부 들을 수 있는 지 여부를 묻는다.
  • 방향 그래프에 사이클이 존재한다면 모든 과목을 수강할 수 없을 것이다.
• 즉 이 문제는 주어진 방향 그래프에 사이클 여부를 묻는 문제이다.
  • 사이클을 찾는 대표적인 알고리즘 위상 정렬을 사용하면 쉽게 풀 수 있다.

접근 방법

1. 들어오는 배열을 사용하기 편한 구조로 변경한다.

2. indegree 가 0인 노드들을 queue에 넣고, 방문 처리하고, 결과 리스트에 넣는다.

3. queue 로 부터 노드를 하나씩 꺼내서 꺼낸 노드와 연결된 노드를 하나씩 방문하며 indegree를 하나씩 줄인다.

4. indegree 가 0인 노드는 queue에 넣고, 방문처리하고, 결과 리스트에 넣는다.

5. queue 가 빌때까지 3, 4 번 과정을 반복한다.

6. 결과 리스트의 숫자와 초기 노드의 숫자가 다르다면 사이클이 있으므로 false를 반환하고 그렇지 않다면 true를 반환한다.

 

코드

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> edges = new HashMap<>();

        int[] indgree = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            edges.putIfAbsent(prerequisite[1], new ArrayList<>());
            edges.get(prerequisite[1]).add(prerequisite[0]);
            indgree[prerequisite[0]]++;
        }

        List<Integer> sortList = new ArrayList<>();
        boolean[] visited = new boolean[numCourses];
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            if (indgree[i] == 0) {
                visited[i] = true;
                sortList.add(i);
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (edges.containsKey(cur)) {
                for (int next :edges.get(cur)) {
                    indgree[next]--;
                    if (indgree[next] == 0) {
                        visited[next] = true;
                        sortList.add(next);
                        queue.add(next);
                    }
                }
            }
        }

        if (sortList.size() != numCourses) {
            return false;
        }
        return true;
    }
}