<Medium> Course Schedule (LeetCode : C#)

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

📕 문제 설명

수강해야할 강좌 수와 선행으로 들어야할 강좌 정보가 주어질 때 주어진 강좌들을 모두 끝낼 수 있는 지에 대한 여부 반환

• Input
  수강해야할 강좌 수 (int), 선행 조건 (int[][])
• Output
  주어진 강좌들을 모두 끝낼 수 있는 지에 대한 여부 (bool)

예제

풀이

결국 트리에 사이클이 있는지 판별하는 문제다. 서로가 서로를 가리키게 되면 수강할 수 없는 상태가 되기 때문! 방향이 있는 그래프이므로 visited와 finished 두 boolean 배열을 만들어서 사이클을 확인했다. (이미 방문한 정점의 dfs가 끝나지 않았는데 해당 정점을 재방문 하는 경우 사이클이 존재한다고 판별)

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        bool[] visited = new bool[numCourses];
        bool[] finished = new bool[numCourses];
        List<List<int>> graph = new List<List<int>>();
        bool answer = true;
        
        for (int i = 0; i < numCourses; i++)
        {
            graph.Add(new List<int>());
        }
        // 선행 조건 관련 그래프 만들기 (방향 o)
        foreach (int[] info in prerequisites)
        {
            graph[info[0]].Add(info[1]);
        }

        for (int i = 0; i < numCourses; i++)
        {
            if (!visited[i]) 
            {
                Traverse(i);
            }
        } 

        return answer;

        void Traverse(int course)
        {
            if (finished[course]) answer = false; // cycle 존재하는 경우 (이미 방문한 곳 방문 시도하므로)
            if (!answer || visited[course]) return;

            visited[course] = true;
            finished[course] = true;

            foreach (int c in graph[course])
            {
                Traverse(c);
            }

            finished[course] = false;
        }      
        
    }
}

결과