Course Schedule - 위상정렬

📌 문제

• [2번 강의를 듣기 위해서는 1번이 필요하다.] 라는 명제를 [2,1]로 표시한다.
• 각 코스들이 '위상정렬' 적으로 돼 있는지 true, false를 출력하라.

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

📌 문제 풀이

🔥 위상 정렬

🔥 풀이

• inDegree의 값이 모두 0이라면 순서대로 들어간 것이므로, true가 나오고, 0이 하나라도 없다면 위상정렬 적으로 이루어진 것이 아니므로 false를 return 한다.

📌 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        int course = 4;
        int[][] nums = {{1,0},
                {2,1},
                {3,2}
        };
        int[][] nums2 = {{1,0},
                {0,1}
        };
        Solution solution= new Solution();
        solution.canFinish(4,nums);
    }
    static class Solution {
        public boolean canFinish(int numCourses, int[][] nums) {
            if(numCourses <=0 ) return false;

            Queue<Integer> queue = new LinkedList<>();
            int[] inDegree = new int[numCourses];

            int numsLength = nums.length;

            // 수강하는 강의들 넣기
            for(int i=0;i<numsLength;i++){
                inDegree[nums[i][1]]++;
            }

            // 최종 목적지 넣기
            for(int i=0;i< inDegree.length;i++){
                if(inDegree[i]==0){
                    queue.offer(i);
                }
            }

            while(!queue.isEmpty()){
                int poll = queue.poll();

                for(int i=0;i<numsLength;i++){
                   if(poll == nums[i][0]){
                       inDegree[nums[i][1]]--;
                       if(inDegree[nums[i][1]] == 0){
                           queue.offer(nums[i][1]);
                       }
                   }
                }
            }
            System.out.println(Arrays.toString(inDegree));
            return true;
        }
    }
}