[Leetcode] 207. Course Schedule - JS
1. 문제 분석
문제분석
--------------------
numCourses: 수강해야 하는 총 강좌의 수
0부터 numCourses - 1까지 레이블이 지정됩니다.
prerequisites[i] = [ai, bi]는 ai를 수강하려는 경우 먼저 bi 강좌를 수강해야 함을 나타낸다.
예를 들어, [0, 1] 쌍은 코스 0을 수강하려면 먼저 코스 1을 수강해야 함을 나타냅니다.
모든 과정을 완료할 수 있으면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.
제한조건
--------------------
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- prerequisites[i]의 모든 쌍은 유일하다.
2. 접근 방법
접근방법
--------------------
prerequisites = [a,b] 인 경우,수강해야 하는 총 과목수(numCourses)가 주어지고,
prerequisites는 0부터 numCourses - 1까지로 구성되니 과목명이 숫자라고 생각하여
graph 구조를 배열로 구성하여 graph의 인덱스는 과목을 의미하고,
해당 인덱스의 값은 과목을 듣기 위한 선행 과목들을 저장한 인접 리스트 배열로 구성할 수 있다.
prerequisites 배열을 순회하여 graph에 과목들의 선행과목(인접리스트)을 저장한다.
문제 예시에서 처럼 0과목을 수강하기 위해 1과목을 수강해야하는데,
1과목을 수강하기 위해 0과목을 수강해야한다면 이는 deadLock(논리적 오류)이므로 이와 같이 순환참조되는 경우가 있는지 확인한다.
visited 배열의 요소는 0이고 길이는 수강과목의 갯수만큼 초기화한다.
visited의 인덱스(과목)이 의미하는 바는 수강과목의 순환체크 상태이다.
0: 순환체크 전
1: 순환체크 중
2: 순환체크 완료
0부터 numCourses - 1까지 과목을 모두 순회하여 hasCycle 함수를 호출하여 검증한다.
hasCycle 함수는
과목을 인자로 받아서 visited 배열에서 과목의 순환체크 상태를 확인 및 변경한다.
과목 상태를 1로 변경한 다음에는
graph에 저장된 해당 과목의 선행 과목들을 참조하여 선행과목을 인자로 hasCycle을 재귀함수로 호출하여 순환을 체크한다.
현재 과목의 선행 과목들의 순환을 체크한다.
선행 과목들의 순환도 마무리했다면 현재 과목의 상태를 2로 바꾸고 현재 과목에 대한 순환 체크 로직을 종료한다.
3. 코드
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function(numCourses, prerequisites) {
// 인접 리스트로 그래프 표현
// 각 코스별 해당 코스를 수강하기 위한 선수 과목들 저장
const graph = Array.from({length:numCourses}, () => []);
// prerequisites를 그래프로 변환
// [1,0]은 "코스 1을 듣기 위해서는 코스 0이 필요하다." -> graph[1].push(0)
for (const [course, pre] of prerequisites) {
graph[course].push(pre)
}
// 방문 상태를 체크할 배열
// 0: 미방문
// 1: 현재 경로에서 방문 중
// 2: 이미 확인 완료된 노드
const visited = new Array(numCourses).fill(0);
// DFS 순환을 검사하는 함수
function hasCycle(course) {
// 현재 경로에서 재방문 -> 순환 발견
if (visited[course] === 1) return true;
// 이미 확인한 노드 -> 순환 없음
if (visited[course] === 2) return false;
// 현재 노드를 방문 중으로 표시
visited[course] = 1;
// 현재 코스의 선수과목들을 확인
for (const pre of graph[course]) {
if (hasCycle(pre)) return true;
}
// 확인 완료 표시
visited[course] = 2;
return false;
}
// 모든 코스에 대해 순환 검사
for (let course = 0; course < numCourses; course++) {
if (hasCycle(course)) return false; // 순환되면 모든 코스 수강 불가
}
return true;
};
4. 복잡도 분석
- 시간복잡도: O(V + E)
- 공간복잡도: O(V + E)
그래프 너무 어렵다... 그래프 구현 자체가 개념이 잘 안잡혀있는 것 같다. 이전 문제와 비교했을 때, 가중 그래프의 경우 노드에 대한 간선들을 Map 자료구조에 저장하고 자료구조 안에서 key는 이웃 노드, value는 가중치로 구현했다.
이번 문제에서는 graph를 방향 그래프로 구현했고, 이 경우 노드에 대한 간선들을 Array 자료구조로 초기화했다.
prerequisites 을 순회하면서 방향을 graph에 적용한다.
[1,0]은 "코스 1"을 듣기 위해 "코스 0"을 선행해야한다. 0 -> 1 이고 이는 graph[1].push(0)으로 나타낸다.
graph[코스번호] = [해당 코스를 듣기 위한 선행과목]
해당 코스에서 순환이 존재하는지 확인하기 위해 dfs 탐색을 한다.
우선 visited 배열에 코스길이 만큼 배열을 요소값은 0으로 초기화한다.
0: 미방문
1: 현재 과목에서 선행과목 확인중(현재 경로에서 방문중)
2: 이미 순환 체크 끝난 과목
위 조건에 따라 visited의 코스들의 값을 변경한다.
dfs 함수 내부에선 visited[수강중인 코스] 값이 1, 2인지 확인하여 순환인지 아닌지 판단한다.
만약 둘다 아니라면 아직 방문하기 전이므로 1로 바꿔 방문중 표시해준다.
그리고 그래프에서 해당 코스의 선행과목을 참조하여 선행과목들이 순환이 있는지 체크한다.
만약 선행과목 중에 dfs 함수를 재귀호출 시 순환이 존재한다면 true를 반환하고
그렇지 않다면 visited[수강중인 코스]를 방문 완료인 2로 변경하고 순환이 없다는 의미로 false를 반환한다.
위의 dfs 재귀 탐색 과정을 모든 수강 코스에 대해 검사해본다.
이 문제에서 수강 코스를 인덱스로 나타냈으므로 visited, graph를 배열로 사용했다.
만약 수강 코스가 인덱스(number)가 아닌 문자열이었다면 Map 자료구조를 사용하는 게 좋을 것 같다.