[アルゴリズムベース]位相位置合わせ
15401 ワード
先決問題
ex)「4科目を履修するためには、1科目を履修しなければなりません.」
受講の順番は?
ノードごとに1度を計算します. のステップ0からQに進む. 0のノードが持つルートのレベルを減算します.
(負の場合、次数が0の場合はqueue) queueのlengthがあるまで繰り返す.
n:ノード総数
m:入力した幹線数
Node:接続された情報
-✔」完全コード
Problem | 列に並ぶ
ex)「4科目を履修するためには、1科目を履修しなければなりません.」
受講の順番は?
アクセス方法
(負の場合、次数が0の場合はqueue)
n:ノード総数
m:入力した幹線数
Node:接続された情報
-✔」完全コード
function solution(n, m, node) {
let answer = [];
let graph = Array.from(Array(n + 1), () => Array().fill(0));
let indegrees = Array(n + 1).fill(0);
let queue = [];
for (let [a, b] of node) {
graph[a].push(b);
indegrees[b]++;
}
// 0인 애들을 첫 스타드 애들로 써야하니까 0 있는 애들은 queue 에 세팅한다
for (let i = 1; i < n + 1; i++) {
if (indegrees[i] === 0) queue.push(i);
}
while (queue.length) {
let check = queue.shift();
answer.push(check);
for (let next of graph[check]) {
indegrees[next]--;
if (indegrees[next] === 0) queue.push(next);
}
}
return answer;
}
位相位置合わせの問題
Problem | 列に並ぶ
const inputs = require("fs")
.readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
.toString()
.split("\n");
let [n, m] = inputs[0].split(" ").map(Number);
let graph = Array.from(Array(n + 1), () => Array());
let indegree = new Array(n + 1).fill(0);
for (let i = 0; i < m; i++) {
let [x, y] = inputs[i + 1].split(" ").map(Number);
graph[x].push(y);
indegree[y]++;
// 그래프 초기화
}
let queue = [];
let answer = [];
for (let i = 1; i <= n; i++) {
if (indegree[i] === 0) queue.push(i);
}
while (queue.length) {
let nx = queue.shift();
answer.push(nx);
for (let next of graph[nx]) {
indegree[next]--;
if (indegree[next] === 0) queue.push(next);
}
}
console.log(answer.join(" "));
Reference
この問題について([アルゴリズムベース]位相位置合わせ), 我々は、より多くの情報をここで見つけました https://velog.io/@mingsomm/알고리즘-위상정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol