[JS][백준]2252_줄 세우기

문제 번호

2252번: 줄 세우기

 

 

알고리즘 분류

• 그래프 이론
• 위상 정렬

 

문제 풀이

 학생들을 '순서'가 있는 방법으로 줄을 세워야 한다.

그래서 위상 정렬을 사용하면 된다. 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 준다.

 항상 알고리즘들이 어떤 조건에서 어떤 결괏값을 내는지(무엇을 구하는 알고리즘인지) 정확히 알고 사용해야 한다.

 

앞에 서야 하는 학생을 front, 뒤에 서야하는 학생을 back이라고 생각하고 front에서 back 방향으로 그래프가 생성되어 있다고 생각한다. 그리고 inDegree배열에는 입력 차수가 몇인지 표시한다.

  const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
  const [N,M] = input[0].split(' ').map(Number);
  let student = input.slice(1).map(_ => _.trim().split(' ').map(Number));
  
  let graph = new Array(N+1).fill(null).map(_ => []);
  let inDegree = new Array(N+1).fill(0);
  for(let i=0; i<student.length; i++) {
    let [front, back] = student[i];
    graph[front].push(back);  // front -> back. front가 어디로 가는지.
    inDegree[back]++; // 진입차수를 표기할 배열.
  }

 

이제 그냥 위상 정렬을 진행하면 된다.

function sol(N,M,graph, inDegree) {
  let answer = '';
  
  let q = new Queue();

  for(let i=1; i<inDegree.length; i++) { // 진입차수가 0인 정점들을 q에 추가한다.
    if(inDegree[i] ===0 ) {
      q.push(i);
    }
  }

  for(let i=1; i<=N; i++) { // 사이클이 안나면 모든 노드를 방문한다.
    if(q.length() === 0) {
      console.log('cycled');
      return;
    }
    
    let cur = q.pop().value;
    answer += cur + ' ';
    for(let j=0; j<graph[cur].length; j++) {  // 연결된 모든 간선을 제거한다.
      inDegree[graph[cur][j]]--;
      if(inDegree[graph[cur][j]] === 0)   // 진입차수가 0이된 정점들을 q에 추가한다.
        q.push(graph[cur][j]);
    }    
  }

  return answer;
}

 

전체 코드

/**
 * ''''''순서가 정해져있는'''''' 작업을 차례로 수행해야할때.
 * 진입차수 0인 정점 큐에 삽입.
 * 큐에서 원소를 꺼내서 열결된 모든 간선제거.
 * 간선 제거 이후 진입차수가 0이된 정점을 큐에 삽입.
 * 큐가 빌때까지 반복. 모든 원소를 방문하기전 큐가 빈다면 사이클이 존재함. 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상정렬의 결과이다.
 */

class Node{
  constructor(value){
    this.value = value;
    this.next = null;
  }
}
class Queue{
  constructor(){
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  length(){
    return this.size;    
  }
  push(value){
    let node = new Node(value);
    if(this.size === 0 ) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }
  pop(){
    let temp = this.head;
    if(this.size <=1 ) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
    }
    this.size--;
    return temp;
  }
}

function main(){
  const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
  const [N,M] = input[0].split(' ').map(Number);
  let student = input.slice(1).map(_ => _.trim().split(' ').map(Number));
  
  let graph = new Array(N+1).fill(null).map(_ => []);
  let inDegree = new Array(N+1).fill(0);
  for(let i=0; i<student.length; i++) {
    let [front, back] = student[i];
    graph[front].push(back);  // front -> back. front가 어디로 가는지.
    inDegree[back]++; // 진입차수를 표기할 배열.
  }
  console.log(sol(N,M,graph,inDegree));
}
function sol(N,M,graph, inDegree) {
  let answer = '';
  
  let q = new Queue();

  for(let i=1; i<inDegree.length; i++) { // 진입차수가 0인 정점들을 q에 추가한다.
    if(inDegree[i] ===0 ) {
      q.push(i);
    }
  }

  for(let i=1; i<=N; i++) { // 사이클이 안나면 모든 노드를 방문한다.
    if(q.length() === 0) {
      console.log('cycled');
      return;
    }
    
    let cur = q.pop().value;
    answer += cur + ' ';
    for(let j=0; j<graph[cur].length; j++) {  // 연결된 모든 간선을 제거한다.
      inDegree[graph[cur][j]]--;
      if(inDegree[graph[cur][j]] === 0)   // 진입차수가 0이된 정점들을 q에 추가한다.
        q.push(graph[cur][j]);
    }    
  }

  return answer;
}
main();

 

특이사항

 문제를 보고 어떤 알고리즘을 써야 할지 생각해보자. 

각 알고리즘이 어떤 상황에 무엇을 구하는지를 알고 있다면 문제에 적합한 알고리즘을 찾을 수 있을 것이다.

위상 정렬의 경우 많이 사용해보지 않은 알고리즘이라 바로 떠올리지 못해서 시간이 오래 걸렸다.