Leet code (Medium) : 207. Course Schedule (BFS) - JAVA

 

특정과목을 수강하려면 선행과목을 수강해야 할수있는데. 주어진 모든 과목을 수강할 수 있는지 확인하는 문제다.

이문제는 dfs, bfs 둘 다 풀수 있으나, bfs가 좀 더 효율적이고 직관적이다. 

맨처음 문제를 보았을 땐 dfs 로 풀어야겠다는 생각을 했지만.. bfs가 더났다.

 

먼저, 이문제의목표는 .. 주어진 n개의 과목을 모두 수강할 수 있는지, 즉 사이클 없이 모든 과목을 완료할 수 있는지를 확인하는 것이다.

이를 위해 prerequisites라는 선행 과목의 제약 조건이 주어지며, 이 조건을 만족할 수 있는 순서대로 모든 과목을 수강할 수 있는지를 판단해야한다.

 

bfs가 더 적합한 이유는 위상 정렬과 사이클 검출이 자연스럽기 때문이다.

이 문제는 방향 그래프에서 사이클이 있는지 확인하는 문제로 볼 수 있다. 사이클이 없으면 모든 과목을 순차적으로 수강할 수 있고, 사이클이 있다면 일부 과목들은 선행 과목을 완료할 수 없으므로 수강이 불가능하다.

 

위상정렬이 있는 그래프(방향성이 있는 그래프) 문제에서 bfs는 방문을 체크하는 visited 객체가 불필요할 수 있다.

진입 차수 배열(이 문제에선 indegree 배열)이 방문 여부를 간접적으로 관리해주기 때문이다.

 

 

class Solution {
    public boolean canFinish(int n, int[][] prerequisites) {
        List<Integer>[] adj = new List[n];  // 선행 과목 넘버를 인덱스로 해서 선행과목의 다음 과목을 담는 리스트.
        int[] indegree = new int[n];    // i 과목을 수강하기 위해 먼저 완료해야할 선행 과목의 수.
        List<Integer> ans = new ArrayList<>();
    
        // 선행해야되는 pair 정보로 인덱스 - 밸류 리스트 adj 채우기 
        for(int[] pair : prerequisites){
            int course = pair[0];   // 현재 과목
            int prerequisite = pair[1]; // 선행 과목
            if(adj[prerequisite] == null){  // 선행 과목의 값이 비어있다면
                adj[prerequisite] = new ArrayList<>();  // 선행과목에 대해 다음 과목 객체 리스트로 생성
            }
            adj[prerequisite].add(course);  // 선행과목을 수강하면 수강할수있는 다음 과목을 add
            indegree[course]++; // 현재 과목의 선행과목 수 ++ ;
        }

        Queue<Integer> queue = new LinkedList<>();
        // 선행 과목이 없는 과목부터 수강하도록 큐에 먼저 추가.
        for(int i = 0; i < n; i++){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }

        // 큐가 다 비워질때까지 반복 (현재 과목을 수강한 과목으로해서 반복)
        while(!queue.isEmpty()){
            int current = queue.poll(); 
            ans.add(current);   // 수강된 과목들을 추가.

            // 다음 수강될 과목으로, 수강 조건이 충족된 과목이 있다면.
            if(adj[current] != null){
                // 그 과목들을 돌면서 수행
                for(int next: adj[current]){
                    indegree[next]--;   // 해당 과목에 대한 선행과목이 수강되었다고 표시
                    if(indegree[next] == 0){    // 만약 선행과목이 모두 수강된 과목일 경우
                        queue.offer(next);  // 해당 과목은 이제 수강될수 있으니 큐에 추가.
                    }
                }
            }
        }

        return ans.size() == n; // 수강된 과목의 수가 목표 과목수와 같다면 true 다르면 false
    }
}