[AG] Course Schedule II / Graph,Topology sort, DFS (JS)

문제

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

//

Graph 위상정렬(Topology sort) 문제이다.

각 Node의 차수(indegree)를 que를 통해 계산해 답을 구하는 방법과, DFS로 구하는 방법 2가지 해결법이 있다.

DFS를 공부중이기 때문에 DFS로 풀어보았다.

풀이

1. Object 혹은 map을 생성하여 주어진 정보를 graph 형태로 나타낸다.
2. numCourses를 0부터 DFS로 순회한다.
3. 위상정렬은 graph에 Cycle이 존재하면 성립될 수 없으므로, Graph의 cycle이 있는지 없는지 검증하는 절차를 DFS에 추가한다.
4. Cycle 검증은 visiting 배열 및 isCycle 변수 생성해 Node별로 DFS 함수가 실행되고 끝날때 add 및 pop을 해주는 방식으로 구현.
5. DFS 순회중 visiting이 겹쳐지면 isCycle = true
6. 또한 visited 배열을 만들어 이미 순회했던 Node는 계산을 건너뛴다.
7. DFS가 그래프의 끝에 도달했을때 visted 처리를 해주고, 순서대로 stack에 넣어준다.
   (DFS가 어떤 노드에서 시작하더라도 상관이 없는 이유)

코드

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
  
    let obj = new Object();
    const visiting = new Set();
    const visited = new Set();
    let stack = [];
    let isCycle = false;
    
    prerequisites.map(arr => {
        const [course, pre] = arr
        obj[course] = [...(obj[course] ?? []), pre]
    })
    
    // console.log(obj)
    
    const DFS = function (v) {
        visiting.add(v)
        let edges = obj[v];
        
        if(edges) {
            for(let e of edges){
                if(visiting.has(e)){
                    isCycle = true;
                    return;
                }
                if(visited.has(e)){
                    continue;
                }
               DFS(e)
            }
        }
        
        visiting.delete(v)
        visited.add(v)
            // console.log(visiting, visited, stack)
        stack.push(v)
    }
    
 
    // console.log(visited)
    // console.log(stack)
    
    for(let i =0; i<numCourses; i++){
        if(!visited.has(i)) DFS(i)
    }
    

   return isCycle ? [] : stack 
};

코드 개선

visited,와 visiting을 변수 하나로 합칠수 있음.

참고 사이트

https://yoongrammer.tistory.com/86