Course Schedule

Course Schedule

LeetCode 207번 문제

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

Course Schedule - LeetCode

 

 

 

 

1. 문제

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.

 

주어진 배열 prerequisites의 원소는 각각 선수과목과 후수 과목을 뜻함.

예를 들어 = [ai, bi]는 ai를 듣기 위해서는 반드시 bi를 들어야 할 것을 뜻함.

주어진 배열 prerequisites에 대해 모든 과목을 수강할 수 있다면 true를 반환, 수강할 수 없는 경우 false를 반환한다.

 

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

 

 

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

 

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

 

 

 

 

2. 풀이

■ 풀이 방법

주어진 배열 prerequisites에 대해 모든 과목을 수강할 수 없는 경우를 판단하고 false를 반환한다. 

 

그렇다면 모든 과목을 수강할 수 없는 경우는 어떤 경우일까?

답은 수강해야 하는 과목의 순서가 "순환"될 때이다.

예를 들어, prerequisites = {{1, 0}, {2, 1}, {0, 2}} 이라고 주어졌다고 하자. 그렇다면 아래와 같은 그래프가 그려질 것이다.

 

[순환 그래프]

0을 들으면 1을 들을 수 있고 1을 들으면 2를 들을 수 있다 그런데 애초에 0을 듣기 위해서는 2를 들어야 한다.

때문에 이런 경우 모든 과목을 들을 수 없다.

 

이처럼 수강과목의 순서가 순환하는 경우 모든 과목을 듣기 위한 조건을 충족할 수 없기 때문에 모든 과목을 수강할 수 없게 된다.

따라서 이 문제를 풀기 위해서는 위와 같은 수강과목의 순서를 나타낸 그래프에서 순환이 일어나는지를 판단하면 된다.

 

그렇다면 순환하는 그래프는 어떻게 찾을 수 있을까?

 

기본적으로 DFS를 사용해서 그래프를 탐색한다.

다만 각 노드는 각 노드까지 탐색된 노드들을 기록하고 있어야 한다.

 

예를 들어 위의 예제에서 0부터 탐색을 시작했다고 하자.

0을 탐색한 뒤에는 1을 탐색하게 될 것이다.

이때 노드 1에서는 탐색된 노드(= {0, 1})를 갖고 있는다.

이후 1 -> 2 방향으로 탐색해서 노드 2에서는 {0, 1, 2}를 갖고 있어야 한다.

이제 2 -> 0 방향으로 탐색이 가능한데 0은 탐색된 노드(={0, 1, 2})에 이미 존재하고 이는 순환이 발생했음을 의미한다.

 

이런 식으로, 각 노드들은 각자 탐색된 경로를 저장하고 DFS를 통해 노드를 탐색할 때 저장된 경로를 통해 순환이 존재하는 지를 판단한다.

 

 

 

■ code

□ staticField

[staticField]

boolean[] check;   //[1]
boolean result = true;   //[2]

● [1] : DFS로 노드를 탐색했을 때, 탐색 여부를 저장하는 배열

● [2] : 최종적으로 반환할 결과의 변수

 

 

□ canFinish

과목 간 순서 그래프를 만들고 DFS를 사용해 순환을 판단하는 메서드

 

[canFinish]

public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList<Integer>[] edges = new ArrayList[numCourses];   //[1]
        check = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            edges[i] = new ArrayList<>();
        }

        for (int[] prerequisite : prerequisites) {   //[2]
            int after = prerequisite[0];
            int before = prerequisite[1];
            edges[before].add(after);
        }

        for (int i = 0; i < numCourses; i++) {
            boolean[] finish = new boolean[numCourses];   //[3]
            dfs(edges, finish, i);   //[4]
        }
        return result;
}

● [1] : 연결 리스트 생성

● [2] : 주어진 배열로 연결 리스트 구현

● [3] : 각 노드에서 저장되야하는 경로가 담길 배열

● [4] : DFS를 사용해서 순환 판단

 

 

□ dfs

DFS를 사용해서 노드를 탐색하고 순환을 판단하는 메서드

 

[dfs]

private void dfs(ArrayList<Integer>[] edges, boolean[] finish , int number) {
        check[number] = true;
        boolean[] tempFinish = finish.clone();
        tempFinish[number] = true;

        ArrayList<Integer> edgeList = edges[number];
        for (Integer integer : edgeList) {
            if (tempFinish[integer]) {
                result = false;
            }
            if (check[integer]) {
                continue;
            }
            dfs(edges, tempFinish, integer);
        }
}

● [1] : 노드를 탐색한 것을 체크

● [2] : 각 노드에서 저장될 경로는 공유되면 안 되기 때문에 clone을 사용해 깊은 복사로 배열을 복사한다.

● [3] : 다음에 탐색될 노드가 저장된 경로(= tempFinish)에 존재한다면 순환이 있는 것이기 때문에 result를 false로 변환해준다.

● [4] : 다음에 탐색될 노드가 이미 탐색되었다면 넘어간다.

● [5] : 다음에 탐색될 노드가 문제가 없다면 dfs를 호출해서 다음 노드를 탐색한다.

 

 

 

■ 전체 코드

[전체 코드]

import java.util.ArrayList;

public class Solution {

    boolean[] check;
    boolean result = true;

    private void dfs(ArrayList<Integer>[] edges, boolean[] finish , int number) {
        check[number] = true;
        boolean[] tempFinish = finish.clone();
        tempFinish[number] = true;

        ArrayList<Integer> edgeList = edges[number];
        for (Integer integer : edgeList) {
            if (tempFinish[integer]) {
                result = false;
            }
            if (check[integer]) {
                continue;
            }
            dfs(edges, tempFinish, integer);
        }
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList<Integer>[] edges = new ArrayList[numCourses];
        check = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            edges[i] = new ArrayList<>();
        }

        for (int[] prerequisite : prerequisites) {
            int after = prerequisite[0];
            int before = prerequisite[1];
            edges[before].add(after);
        }

        for (int i = 0; i < numCourses; i++) {
            boolean[] finish = new boolean[numCourses];
            dfs(edges, finish, i);
        }
        return result;
    }
}