-
https://leetcode.com/problems/course-schedule-ii/
// ___________________문제___________________
// 모든 경로를 탐색하며 레벨을 올라가기
// __________________Syntax__________________
//
// ________________Algorithms________________
//
// ____________________Input___________________
// prerequisites: [[4, 2], [4, 1], [2, 3], [2, 1], [3, 0], [2, 0], [1, 0]];
// prerequisites: [[1,0],[2,1],[0,2]];
1. 내 풀이
let graph;
let visited;
let visiting;
var findOrder = function (numCourses, prerequisites) {
graph = new Map();
visited = new Set();
visiting = new Set();
let allNumbers = new Set();
for ([e, s] of prerequisites) {
let edges = graph.get(e) || [];
edges.push(s);
graph.set(e, edges);
allNumbers.add(s);
allNumbers.add(e);
}
for(let i = 0; i < numCourses; i++) {
if(allNumbers.has(i)) {
continue;
}
visited.add(i);
}
for ([e, s] of graph) {
let hasCycle = backTracking(e);
if(hasCycle === false) {
return [];
}
}
return [...visited];
};
var backTracking = function (node) {
let edges = graph.get(node);
visiting.add(node);
if (edges) {
for (s of edges) {
if (visited.has(s)) {
continue;
} else if (visiting.has(s)) {
return false;
}
let hasCycle = backTracking(s);
if(hasCycle === false) {
return false;
}
}
}
visiting.delete(node);
visited.add(node);
}
2. https://leetcode.com/problems/course-schedule-ii/discuss/420402/Clean-JavaScript-solution
const findOrder = (numCourses, prerequisites) => {
const inDegrees = new Array(numCourses).fill(0);
// [0, 1, 2, 1, 2]
for (const [v] of prerequisites) {
inDegrees[v]++;
}
const q = [];
for (let i = 0; i < inDegrees.length; i++) {
const degree = inDegrees[i];
if (degree === 0) q.push(i);
}
const res = [];
while (q.length) {
const u0 = q.shift();
numCourses--;
res.push(u0);
for (const [v, u] of prerequisites) {
if (u === u0) {
inDegrees[v]--;
if (inDegrees[v] === 0) q.push(v);
}
}
}
return numCourses === 0 ? res : [];
};
'알고리즘 > 리트코드' 카테고리의 다른 글
1043. Partition Array for Maximum Sum (0) 2021.05.27 542. 01 Matrix (0) 2021.05.27 207. Course Schedule (0) 2021.05.23 1277. Count Square Submatrices with All Ones (0) 2021.05.23 152. Maximum Product Subarray (0) 2021.05.23 댓글