[JS] 위상 정렬

1. 위상 정렬

 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.  [그림 1]을 보자. [그림 1]은 임의로 만든 마법사로 전직을 한후 배워야하는 스킬의 관계도다.

 

[그림 1] 스킬 관계도

 

 각 스킬에 대한 관계도를 정리하면 다음과 같다.

 

1. 에너지 볼트는 맨 처음에 배우는 기본 마법이다.

2. 매직클로를 배우려면 에너지볼트를 먼저 배워야한다.

3. 메테오를 배우려면 먼저 매직클로, 텔레포트를 배워야한다.

4. 마력 흡수를 배우려면 먼저 에너지 볼트를 배워야한다.

5. 텔레포트를 배우려면 먼저 마력흡수, 매직클로를 배워야한다.

 이러한 흐름은 조건을 걸어줘서 해석할 수 있다. 먼저 마법사로 전직하면 에너지 볼트를 찍고, 그 다음엔 마력 흡수 또는 매직클로를 찍는다. 그리고 텔레포트를 찍고 최종적으로 메테오를 찍어서 마스터 마법사가 되어야한다.

 

스킬 찍는 순서: 에너지볼트 → 마력 흡수 → 매직클로 → 텔레포트 → 메테오 

 

 위와 같은 순서로 스킬을 찍는다면 우리는 마스터 마법사가 될 수 있다. 물론 마력 흡수 말고, 매직클로를 먼저 찍는 방법도 있다. 위상 정렬은 사이클이 존재하지 않는 방향 그래프여야 한다는 전제조건이 있다. 사이클이 발생하면, 시작점이 없기 때문에 위상 정렬을 수행할 수 없기 때문이다.

 

 

 위상 정렬을 수행하는 알고리즘은 큐를 이용하는 방식, 스택을 이용하는 방식이 존재한다. 이번 포스팅에서는 큐를 이용하여 위상 정렬을 구현해보도록 하겠다. 큐를 이용하는 방법은 다음과 같다.

 

1. 진입 차수가 0인 정점을 큐에 삽입한다.

2. 큐에서 원소를 꺼내 모든 간선을 제거한다.

3. 간선 제거 이후 진입차수가 0인 정점을 큐에 삽입한다.

4. 큐가 빌 때 까지 2-3번 과정을 반복한다.

 

이제 스킬트리를 예시로 들어서 위상 정렬이 어떤 과정으로 돌아가는지 설명해보도록 하겠다. 먼저 에너지 볼트를 배운다(큐에 삽입 후 데이터 POP). 그리고 에너지 볼트와 연결된 간선을 모두 지운다. 따라서 매직 클로, 마력 흡수를 배우기 위해 필요한 선행 스킬 수는 0이 된다.

 

[그림 2] 1 단계

 

 이제 매직클로, 마력흡수를 배우기 위해 필요한 선행 스킬수가 0이므로 매직클로, 마력흡수 정점 모두 큐에 삽입한다.

 

[그림 3] 2 단계

 

 큐에 있는 마력흡수 데이터를 빼서 마력흡수를 배우도록 하자. 그리고 마력 흡수에 연결되어 있는 간선을 모두 제거한다. 따라서 텔레포트마법을 배우기 위해 필요한 마법 수는 0이 아니라 1이므로, 큐에 삽입하지 않는다.

 

[그림 4] 3 단계 

 

 이제 큐 데이터가 비워질 때 까지 이 과정을 계속 반복하면 된다.

 

 

프로그램은 다음과 같다.

// 각 스킬 정보 
const Skill = function(key, data){
  this.key = key;
  this.data = data;
  this.nextSkill = null;
}

const SkillTree = function(){
  this.skillbook = [];
  this.preNeeds = [];

  // 스킬 북 리턴
  SkillTree.prototype.getSkillBook = function(){
    return this.skillbook;
  }

  // 각 스킬을 배우는데 필요한 선행 마법의 수
  SkillTree.prototype.getPreNeeds = function(){
    return this.preNeeds;
  }

  //키워드, 스킬이름을 파라미터로 받아 스킬북에 스킬을 추가한다.
  SkillTree.prototype.makeSkill = function(key, name){
    const skillbook = this.skillbook;
    const newSkill = new Skill(key, name);
    skillbook[key-1] = newSkill;
    this.preNeeds[key-1] = 0; // 스킬을 배우는데 필요한 선행 스킬 수를 0으로 초기화
  }

  // 해당스킬에 배워야하는 스킬 추가(방향 그래프)
  SkillTree.prototype.makeSkillTree = function(k1, k2){
    // k1: 배워야하는 스킬 키 값
    // k2: 해당 스킬 키 값
    let skill = this.skillbook[k1-1];
    const k2Skill = this.skillbook[k2-1];
    while(skill.nextSkill !== null){
      skill = skill.nextSkill;
    }
    skill.nextSkill = new Skill(k2, k2Skill.data);
    this.preNeeds[k2-1]++; 
    //해당 스킬 인덱스에 배워야 하는 스킬 수 1 추가
  }

  // 출력: 해당스킬: 배워야하는 스킬들
  SkillTree.prototype.printSkillTree = function(){
    const skillbook = this.skillbook;
    const size = skillbook.length;
    // size 길이의 문자열 배열 생성 후 모든 요소에 '' 값을 초기화
    let strs = new Array(size).fill('');

    for(let i=0; i<size; i++){
      // 배워야하는 스킬
      let skill = skillbook[i];
      let preskill = skill.data;

      while(skill.nextSkill !== null){
        // 해당 스킬 검색
        skill = skill.nextSkill;
        const idx = skill.key-1;
        // 해당 스킬 인덱스에 ''값만 있을 경우, 해당 스킬 데이터  삽입
        if(strs[idx] === ''){
          strs[idx] = `${skill.data}:`;
        }
        // 기존 데이터에 배워야하는 스킬 이름 추가
        strs[idx] += ` ${preskill},`;
      }
    }

    for(let i=0; i<size; i++)
      if(strs[i])
        console.log(strs[i].substr(0, strs[i].length-1));
  }
}

const topologySort = function(skillbook, preNeeds){
  const size = skillbook.length;
  const q = [];
  let count = 1;
  let result = '';

  q.push(skillbook[0]);

  // 큐가 빌 때 까지
  while(q.length){
    let skill = q.pop();
    result += `${count++}.${skill.data} `;
    while(skill.nextSkill !== null){
      skill = skill.nextSkill;
      const curKey = skill.key-1;
      preNeeds[curKey]--;

      if(!preNeeds[curKey])
        q.push(skillbook[curKey]);
    }
  }

  console.log(result);

}

const main = (function(){
  const skillTree = new SkillTree();
  
  skillTree.makeSkill(1, '에너지 볼트');
  skillTree.makeSkill(2, '매직 클로');
  skillTree.makeSkill(3, '메테오');
  skillTree.makeSkill(4, '마력 흡수');
  skillTree.makeSkill(5, '텔레포트');

  skillTree.makeSkillTree(1, 2);
  skillTree.makeSkillTree(1, 4);

  skillTree.makeSkillTree(2, 3);
  skillTree.makeSkillTree(2, 5);

  skillTree.makeSkillTree(4, 5);
  skillTree.makeSkillTree(5, 3);

  console.log(" A(마법): B(선행 마법) ");
  console.log("---------------------------------")
  skillTree.printSkillTree();

  const skillbook = skillTree.getSkillBook();
  const preNeeds = skillTree.getPreNeeds();

  console.log("\n\n권장 스킬 트리");
  topologySort(skillbook, preNeeds);
}());

 

 

2. 참고 자료

• 안경잡이 개발자 - 25. 위상 정렬(Topology Sort)