선행관계가 있는 문제
ex ) ' 4라는 과목을 수강하기 위해서는 1과목을 수강해야한다. '
수강해야하는 순서는?
queue의 length 가 있을 때까지 반복해준다.
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(" "));