[알고리즘기초] 위상정렬

Urther·2021년 11월 23일
0

알고리즘개념

목록 보기
3/5

선행관계가 있는 문제

ex ) ' 4라는 과목을 수강하기 위해서는 1과목을 수강해야한다. '

수강해야하는 순서는?

✨ 접근 방식

  • 각 노드 마다 indegree를 계산해준다.
  • indegress가 0인 것부터 큐에 push 해준다.
  • 0인 노드가 가진 노선의 indegree를 마이너스해준다.
    ( 마이너스해줄 때, indegree 가 0이 된다면 queue에 push 해준다)

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(" "));
profile
이전해요 ☘️ https://mei-zy.tistory.com

0개의 댓글