Course Schedule - LeetCode

문제 접근 🤔

• 어떤 지점을 방문하기 위해 방문해야 하는 선행 방문 지점이 주어질 때, 주어진 코스가 순회 가능한지 여부를 구하는 문제이다.

• 예를 들어 1을 방문하기 위해서 0을 방문해야 하고, 0을 방문하기 위해서 1을 방문해야 한다면, 두 지점 모두 방문이 불가능하므로 코스가 순회가 불가능하다고 할 수 있다.

• 문제에서 주어진 prerequisites 를 그래프의 간선으로 생각해 그래프로 모델링 한 후, 그래프에서 사이클이 존재하면 코스가 순회 불가능, 사이클이 존재하지 않으면 코스가 순회가 가능하다고 판단해주면 된다.

• visited 로 방문점 파악, traced 로 사이클 존재 여부를 파악하게 하여 코드를 작성하였다.

• 방문점, 사이클 존재 파악시 in을 사용하면 시간복잡도가 O(N)이라 비효율적인 코드가 아닌가 하는 생각이 들 수 있다.

• 파이썬의 경우 list, tuple 자료형에서는 in 사용시 하나하나 순회하기 때문에 O(N)이지만, set이나 dictionary에서는 내부적으로 hash를 통해서 자료들을 저장하기 때문에 해시 충돌이 정말 많이 발생하지 않는 이상 O(1)로 작동한다.
  
  
  

놓쳤던 부분 😅

• 이 문제는 반쪽짜리 풀이만 하고 잘 생각이 안 나서 다른 풀이를 참고하였다.

• 파이썬으로 먼저 풀이 후, JS로 변환했는데 답이 달라서 삽질의 시간을 가졌다.

• 문제는 forEach 구문에서 return 을 하려고 했던 것. forEach 문에서 break , continue 를 쓸 수 없다는 건 알고 있었지만 return 도 안 먹힌다는걸 망각하고 함수를 종료시키려고 했다.

• forEach 는 예외를 던지지 않고는 멈추지 못한다. 중간에 멈춰야 한다면 for문을 사용하자.

• 기본적인 실수를 한 것에 반성하기.
  
  
  

코드 😁

파이썬 코드(90 ms)

from collections import defaultdict

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = defaultdict(list)
        traced, visited = set(), set()
        for first, finish in prerequisites:
            graph[first].append(finish)

        def dfs(first):
            #  순환 구조이면 False
            if first in traced:
                return False
            # 이미 방문했던 노드이면 True
            if first in visited:
                return True
            
            traced.add(first)
            visited.add(first)
            for next in graph[first]:
                if not dfs(next):
                    return False
            # 탐색 종료 후 순환 노드 삭제
            traced.remove(first)

            return True
        
        # 순환 구조 판별
        for x in list(graph):
            if not dfs(x):
                return False
        return True

자바스크립트 코드(61 ms)

const canFinish = (numCourses, prerequisites) => {
  const graph = {};
  const traced = new Set();
  const visited = new Set();
  prerequisites.forEach(([first, finish]) => {
    if (!graph[first]) {
      graph[first] = [];
    }
    graph[first].push(finish);
  });

  const dfs = (first) => {
    // 순환 구조이면 false
    if (traced.has(first)) {
      return false;
    } // 이미 방문했던 노드이면 true
    if (visited.has(first)) {
      return true;
    }

    traced.add(first);
    visited.add(first);
    if (first in graph && !!graph[first].length) {
      for (let i = 0; i < graph[first].length; i++) {
        if (!dfs(graph[first][i])) {
          return false;
        }
      }
    }
    // 탐색 종료 후 순환 노드 삭제
    traced.delete(first);
    return true;
  };
  // 순환 구조 판별
  const keyList = Object.keys(graph);
  for (let i = 0; i < keyList.length; i++) {
    if (!dfs(keyList[i])) {
      return false;
    }
  }
  return true;
};