[アルゴリズムベース]位相位置合わせ


先決問題
ex)「4科目を履修するためには、1科目を履修しなければなりません.」

受講の順番は?

アクセス方法

  • ノードごとに1度を計算します.
  • のステップ0からQに進む.
  • 0のノードが持つルートのレベルを減算します.
    (負の場合、次数が0の場合はqueue)
  • 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(" "));