📌 문제 설명

Course Schedule 문제 보기

📌 문제 접근

사이클이 있는지만 확인하면 되는 문제. 그리고 양방향도 아니기 때문에 graph 배열을 만들고, visited 배열을 통해 방문 상태를 기록했다.

그리고 조기종료를 통해 효율성을 높였다. 간단한 문제.

📌 내가 작성한 코드

const canFinish = (numCourses, prerequisites) => {
  const graph = prerequisites.reduce(
    (acc, cur) => {
      acc[cur[1]].push(cur[0]);
      return acc;
    },
    Array.from({ length: numCourses }, () => []),
  );

  const visited = new Array(numCourses).fill(0);

  const dfs = (now) => {
    if (visited[now] === 1) return false;
    if (visited[now] === 2) return true;
    visited[now] = 1;
    for (const next of graph[now]) {
      if (!dfs(next)) return false;
    }
    visited[now] = 2;
    return true;
  };

  for (let i = 0; i < numCourses; i++) {
    if (visited[i] === 0 && !dfs(i)) return false;
  }

  return true;
};

📌 시간 복잡도

O(V + E) - 모든 노드와 간선을 한 번씩 방문하므로 (V: 코스 수, E: 선수조건 수)

📌 참고 링크

• Array.reduce() - MDN