baekjoon. 줄 세우기

문제

링크

풀이

위상 정렬을 이용하면 된다

코드

  function init(compares, N) {
    const edge = Array(N+1).fill().map(()=>0);
    const adj = Array(N+1).fill().map(()=>[]);

    compares.forEach(compare=>{
      const [b, s] = compare.split(' ').map(v=>v*1);
      edge[s]++;
      adj[b].push(s);
    });

    return [edge, adj];
  }
  function check (edge, que, i){
    if(!edge[i]){
      que.push(i);
      edge[i] = -1;
    }
  }

  function solution(input){

    const [N, _] = input.split('\n')[0].split(' ').map(v=>v*1);
    const compares = input.split('\n').slice(1);

    const [edge, adj] = init(compares, N);

    const que = [];

    for(let i=1; i<=N;i++){
      check(edge, que, i);
    }
    const answer = [];
    while (que.length){
      const temp = que.shift();
      answer.push(temp);

      adj[temp].forEach(v=>{
        edge[v]--;
        check(edge,que,v);
      });
    }
    console.log(answer.join(' '));
  }