210. Course Schedule II

문제

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

코드

import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> g[] = new List[numCourses];
        int dp[] = new int[numCourses];
        boolean visit[] = new boolean[numCourses];
        List<Integer> res = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();


        for(int i=0; i<g.length; i++)
            g[i] = new ArrayList<>();

        for(int i=0; i<prerequisites.length; i++){
            g[prerequisites[i][1]].add(prerequisites[i][0]);
            dp[prerequisites[i][0]]++;
        }

        for(int i=0; i<numCourses; i++){
            if(dp[i] == 0){
                visit[i] = true;
                q.add(i);
            }
        }

        while(!q.isEmpty()){
            int curNode = q.poll();
            res.add(curNode);
            for(int node : g[curNode])
                dp[node]--;
            for(int i=0; i<numCourses; i++){
                if(dp[i] == 0 && visit[i] == false){
                    visit[i] = true;
                    q.add(i);
                }
            }
        }

        for(int i=0; i<numCourses; i++)
            if(dp[i] != 0)
                return new ArrayList<Integer>().stream().mapToInt(Integer::intValue).toArray();

        System.out.println(res);

        return res.stream().mapToInt(Integer::intValue).toArray();

    }
}

피드백

• 전형적인 위상정렬 문제였다.
  • bfs 방식이 내가 익숙한 방식임
  • 위상 정렬을 잘 설명한 다른 블로그이다.https://yoongrammer.tistory.com/86#%EC%9C%84%EC%83%81_%EC%A0%95%EB%A0%AC(Topological_sort)
• 위상정렬이 아닌 경우를 찾는 것은 그냥 dp를 확인해서 모두 0이 아니면 문제가 있다고 판단하고 했더니 되더라.