Course Schedule

특정 강의를 듣기 위해서 다른 강의를 들어야 하는 정보가 주어질 때 정상적으로 강의를 들을 수 있는 지에 대한 문제이다. 강의의 관계가 순환 참조 되는 경우 불가능하다고 판단해야 한다.

 

처음에는 dfs 백트래킹 방식으로 해결하려 하였으나 시간 초과가 되었다. 알고리즘을 바꿔야 하나 고민도 했지만 같은 관계를 여러 번 반복해서 검사를 수행하는 경우가 생긴다는 문제를 알게 되었다. 동일 경로에 대해 어떻게 처리할까 고민하던 중 일반적인 visited를 boolean으로 사용하는 방식 대신 int를 이용하여 미방문,방문,경로완료의 형태로 세가지 상태로 visited 배열을 관리하여 해결해 보았다. 결과적으로 시간 초과의 문제를 해결하고 통과할 수 있었다.

import java.util.*;  
  
public class Solution {  
  
    static int VISITED = 1;  
    static int COMPLETE = 2;  
  
    public boolean canFinish(int numCourses, int[][] prerequisites) {  
        List<Integer>[] preCourse = new ArrayList[numCourses];  
        for(int i = 0; i < numCourses; i++){  
            preCourse[i] = new ArrayList<Integer>();  
        }  
  
        for(int[] info : prerequisites){  
            int course = info[0];  
            int need = info[1];  
  
            preCourse[course].add(need);  
        }  
  
        int[] visited = new int[numCourses];  
        for(int i = 0; i < numCourses; i++){  
            if(preCourse[i].isEmpty()) continue;  
            if(!isPossible(i, preCourse, visited)){  
                return false;  
            }  
        }  
  
        return true;  
    }  
  
    private boolean isPossible(int course, List<Integer>[] preCourse, int[] visited){  
  
        if(visited[course] == COMPLETE){  
            return true;  
        }  
  
        if(visited[course] == VISITED){  
            return false;  
        }  
  
        visited[course] = VISITED;  
  
        for(int pre: preCourse[course]){  
            if(!isPossible(pre, preCourse, visited)){  
                return false;  
            };  
        }  
  
        visited[course] = COMPLETE;  
        return true;  
    }  
  
}