[알고리즘] Leetcode_207_Course_Schedule

Problem

Solve

• 2차원 배열 prerequisites[i] = [ai, bi] 는 b를 선수 이수하여야 a를 들을 수 있다. 이를 그래프로 나타내면 b ➡️ a 로 나타낼 수 있다.

  • 그래프 표현을 위해 Map<Integer, List<Integer> graph 혹은 List<List<Integer>> graph 로 나타낼 수 있다.

• 예제 2를 그래프로 나타내면 0 ➡️ 1 / 1 ➡️ 0 인데, 서로가 선수과목이라고 주장하는 것이다. 이를 쉽게 말하면 사이클이 생기는 경우라고 할 수 있다. 즉, 사이클이 생기는 경우에 false를 반환하면 되는 것이다.

  • dfs 재귀하면서 사이클이 생기는 경우에 대해 공부하다가 참고자료 가 아주 유용했다.

• 두 가지 배열이 필요하다. 먼저 어떤 노드를 방문했는지에 대한 방문여부를 체크하는 visited 배열과 그래프에서 순환을 체크하기 위해 일종의 재귀 호출 스택을 나타내는 recStack 배열이다.

  • visited: 방문한 노드를 체크하기 위한 배열. 그래프의 각 노드를 방문할 때마다 해당 노드를 visited 배열에 표시하여 방문된 노드임을 표시한다. 이미 방문된 노드인 경우, 해당 노드가 다시 방문되는 것을 방지하기 위해 visited 배열을 확인하고 방문하지 않았다면 방문 전 사이클인 지 재귀함수를 통해 확인한다.

  • recStack: 순환을 체크하기 위한 재귀 호출 스택. 그래프의 각 노드를 방문할 때마다 해당 노드를 recStack에 추가하고, 재귀 호출이 끝날 때 해당 노드를 스택에서 제거함으로써 순환을 체크한다. 순환 그래프인 경우, 현재 방문 중인 노드가 이미 recStack에 존재하는 경우에는 순환으로 간주하고 순환을 체크하여 isCycle 함수에서 true 를 반환한다.

1. Map 사용

class Solution {
    public boolean isCycle(Map<Integer, List<Integer>> graph, boolean[] visited, boolean[] recStack, int start) {
        visited[start] = true;
        recStack[start] = true;

        if (graph.containsKey(start)) {
            for (int next : graph.get(start)) {
                if (!visited[next]) {
                    if (isCycle(graph, visited, recStack, next)) {
                        return true;
                    }
                } else if (recStack[next]) {
                    return true;
                }
            }
        }

        recStack[start] = false;
        return false;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            int next = prerequisite[0];
            int prev = prerequisite[1];
            if (!graph.containsKey(prev)) {
                graph.put(prev, new ArrayList<>());
            }
            graph.get(prev).add(next);
        }

        boolean[] visited = new boolean[numCourses];
        boolean[] recStack = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && isCycle(graph, visited, recStack, i)) {
                return false;
            }
        }
        return true;
    }
}

2. 이중 리스트 사용

class Solution {
    public boolean isCycle(List<List<Integer>> graph, boolean[] visited, boolean[] recStack, int start) {
        visited[start] = true;
        recStack[start] = true;

        List<Integer> nextSubjects = graph.get(start);
        for (int next : nextSubjects) {
            if (!visited[next]) {
                if (isCycle(graph, visited, recStack, next)) {
                    return true;
                }
            } else if (recStack[next]) {
                return true;
            }
        }

        recStack[start] = false;
        return false;
    }

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

        for (int[] prerequisite : prerequisites) {
            int next = prerequisite[0];
            int prev = prerequisite[1];
            graph.get(prev).add(next);
        }

        boolean[] visited = new boolean[numCourses];
        boolean[] recStack = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && isCycle(graph, visited, recStack, i)) {
                return false;
            }
        }
        return true;
    }
}

그림으로 이해하기

1. 사이클이 아닌 경우
   

2. 사이클인 경우