[알고리즘] LeetCode 207. Course Schedule JS

개요

numCourse와 prerequisites 두 배열이 매개변수로 주어진다.

prerequisites는 각 numCourse에 대한 선 이수과목 정보가 주어진다.

 

예를들어 numCourse가 2라면 과목이 2개 있다는 뜻이고 prerequisites가 [1,0]으로 주어진다면 1을 이수하려면 0과목을 먼저 이수해야된다는 말이된다 따라서 0을 먼저 이수하면 전 과목을 이수할 수 있으니 true를 리턴한다. 만약 numCourse 2일때 prerequisites [1,0] [0,1]로 주어진다면 1을 이수하기 위해선 0과목을 먼저 이수해야되지만 반대로 0과목을 이수하기 위해선 1과목을 이수해야한다는 모순(싸이클)이 발생한다. 이렇게 되면 전과목을 이수할 수 없기 때문에 false를 반환해야한다.

Course Schedule - LeetCode

 

풀이

우선 문제를 보면 금방 알 수 있지만 그려서 표현해보면 그래프로 구현될 수 있다. 이렇게 구현된 그래프에서 순환 구조, 즉 사이클이 발생하는지를 검사하면 전부 이수될 수 있는지를 확인할 수 있으니 사이클을 찾아서 확인한다.

 

DFS로 구현했고 그래프를 전부 탐색할 수 있는지 사이클이 발생할 수 있는지를 temp 배열을 통해 이미 들어가 있는 원소가 중복되어 들어가는 것을 검사했다. 

 

그런데 처음 구현했을 때 문제를 잘못 확인해서 한번 틀렸고 두 번째는 시간초과 에러가 발생을 했다.

답을 참고했더니 메모이제이션을 활용하는거 같았다

따라서 visited 배열을 둬서 이미 탐색한 배열이라면 패스하도록 구현했고 무사히 풀어낼 수 있었다.

 

/*
 * @lc app=leetcode id=207 lang=javascript
 *
 * [207] Course Schedule
 */

// @lc code=start
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 *
 * numCourses로 총 들을 수 있는 코스의 수가 주어지는데
 * 이때 주어진 numCourse만큼 모든 코스를 수강할 수 있으면 true
 * 아니면 false를 리턴하는 문제이다.
 *
 * 1. 순환구조가 되어서는 안된다.
 * 0을 들으려면 1이 필요하고 1을 들으려면 0이 필요한 구조
 *
 * 2. numCourses만큼 코스를 다 돌아야한다.
 * Graph
 */
var canFinish = function (numCourses, prerequisites) {
  //선행 과목이 앖는 노드는 무조건 들을 수 있으니 그래프에서 포함되지 않는다.
  //순환구조가 만들어지면 안된다, 한가지 과목을 들으려면 여러개의 선행과목이 필요할 수 있다.
  const graph = new Map();
  const visited = [];
  const temp = [];

  //그래프 만들기 v에 대해 e값
  for (let [v, e] of prerequisites) {
    graph.set(v, [...(graph.get(v) || []), e]);
  }

  const DFS = (v) => {
    const edges = graph.get(v);
    if (!edges) return false;
    else {
      for (const edge of edges) {
        if (visited.includes(edge)) continue;
        if (edge === v || temp.includes(edge)) return true;
        temp.push(edge);
        if (DFS(edge)) return true;
        temp.pop(edge);
        visited.push(edge);
      }
    }
  };

  for (const [v, e] of graph) {
    if (DFS(v)) {
      return false;
    }
  }

  return true;
};
// @lc code=end

회고

그래프는 많이 안풀어봐서 헷갈리는게 많은거같다..