[LeetCode] 207.Course Schedule 👏새로운개념

Course Schedule - LeetCode

문제 이해하기

(00:90 해결x -> 개념 찾아봄..)

numCourses 개 만큼의 코스가 존재한다. 0 ~ numCourses-1 의 라벨이 매겨져 있다.

prerequisites[i] 는 int[2] 짜리 배열로, prerequisites[i][1] 은 prerequisites[i][0] 인 과목의 선수과목이다. 즉, prerequisites[i][1] 을 들어야만 prerequisites[i][0] 을 수강할 수 있다.

이러한 정보들이 주어질 때, 모든 코스를 끝낼 수 있다면 true를 리턴, 그렇지 않으면 false를 리턴하라.

---

이 문제는 왠지 문제 이해가 핵심인 것 같다.

• 모든 과목을 들을 수 있는지 확인하기 위해 count를 하거나
• visit을 만들던가 해야할 것 같다

예시2는 마치 데드락과 같은 상황... 서로가 선수조건으로 서로를 원하고 있음

• 즉, 불가능한 경우 ? → cycle이 생기는 경우
• 이 문제는 unique한 prerequisite 만을 준다고 하였음

문제 풀이 ( 새로운 개념 )

단방향 그래프에서 싸이클을 찾아야 하는 상황이다.

이 문제는 하나하나에 대해 dfs를 한다면 시간초과가 나올 것이다.

• 그럼 어떻게 풀어야하지?? 단방향 그래프에서 싸이클이 생겨나는 것을 어떻게 알 수 있을까? 기존에 유니온 파인드 방식으로 해 보려니, 이는 합집합을 구하는 거라 상황에 맞지 않는 듯 했다. ( 양방향또는 무방향 그래프일 때 적용.. )

그래프에서 DFS로 싸이클 찾기

• 모든 노드에서 dfs를 하며 자기자신에게 오는지 확이하는 것은 백프로 시간초과였다.

그래프에서 DFS로 사이클 찾기

• dfs 를 사용하여 재귀적으로 그래프의 노드들을 타고 흘러가기 때문에 이 방식을 사용할 수 있다.
  • 즉, dfs 를 통해 x 노드를 방문
    • 해당 노드가 이미 방문 되었음 && 그런데 이 노드를 거쳐간 dfs 함수가 아직 호출종료 되지 않음 ( 그럼에도 다시 이 노드를 방문했다는 것은 → cycle이 존재한다는 의미와 같음 )
• 따라서 이 과정을 위해

  • 노드의 방문여부를 확인하는 테이블

  • 함수의 종료 여부를 확인하는 테이블

  • 둘 다 false로 초기화 시켜놓는것

    이 필요하다.

class Solution {
    // 인접 리스트 그래프 
    public ArrayList<Integer>[] graph = new ArrayList[100001];
    // 방문 여부 
    public boolean[] visit;
    // 함수 호출 종료 여부
    public boolean[] finish;
    // 싸이클 존재여부
    public boolean cycle;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // init table
        visit = new boolean[numCourses]; 
        finish = new boolean[numCourses];
        //===== init graph ====
        for(int i=0;i < numCourses ; i++)
            graph[i] = new ArrayList<Integer>();
        // prerequisites[i][0] 의 부모노드 prerequisites[i][1]
        for(int[] c:prerequisites){
            graph[c[0]].add(c[1]);
        }
        
        // 일단 모든 노드를 시작으로 한다 
        for(int i =0 ;i<numCourses;i++){
            dfs(i);
            if(cycle) break;
        }
        // cycle이 존재함 -> 끝낼 수 없음 
        // cycle이 존재하지 않음 -> 끝낼 수 있음 
        return !cycle;
        
    }
    
    // cur 노드를 방문
    public void dfs(int cur){
        if(visit[cur]){
            // 이미 이 cur을 다녀간 dfs 함수가 아직 진행중 ( 인데 또 방문했다는 것은 cycle이 존재함을 뜻함)
            if(!finish[cur])cycle = true;
            // 중복 방문은 안되니까 (기하급수적으로 늘어나버림 )
            return;     
        }
        visit[cur] = true;
        // 인접 노드들을 방문
        for(Integer adj : graph[cur]){
            dfs(adj);
        }
        finish[cur] = true;
    }
}

🚀 DFS와 cycle

dfs를 사용하여 cycle여부 확인이 가능함을 새로 알게되었음 - dfs 를 사용하며 가지치기만 잘 하면 거의 O(V+E) 로 문제를 푸는게 가능하다