cycle detection1 course schedule Course Schedule prerequisite : [a,b] = a course를 완료하기 위해 b course를 먼저 완료 해야함 numCourses : 코스 개수, prerequisites 가 주어졌을때 전부 완료가능하면 True 아니면 False Solution1 각 course 를 node 로 prerequisite 를 edge 로 생각하면 directed graph로 표현가능 directed graph에 cycle 이 존재하는 지 판별해서 존재하는 경우 False, 없으면 True dfs를 이용해 한 노드에서 출발하는 경로중에 cycle이 존재하는 지 검사할수 있음(has_cycle) 방문한 노드 기록(visitied) 해당 노드를 출발점으로 하는 어떤 경로에도 cycle이 없다고 결정(f.. 2022. 1. 21. 이전 1 다음