[알고리즘] 위상 정렬 (Topology Sort)

  목  차

• 위상정렬(Topological Sorting)
• 기본 개념 및 조건
• 위상정렬을 구현하며 배운 것들
• 구현 방법

 

 

---

 

  위상정렬(Topological Sorting)

 

위상정렬은 방향이 있는 그래프에서 유효하다. 예를 들면, 여러 작업이 서로 의존 관계를 가질 때, 어떤 순서로 작업을 진행해야 하는지를 결정할 때 유용하다. 

 

위상정렬은 결과가 매 번 다를 수 있다. 예를 들면, 4는 2의 앞에 있어야 하고, 3은 1의 앞에 있어야 한다고 가정할 때

예상되는 경우의 수는 4231, 4321, 4312 등 여러 개가 될 수 있다. 

 

 

 

 

---

 

  기본 개념 및 조건

 

• 방향성 그래프: 각 간선에 방향이 있는 그래프여야 한다.
• 단방향 그래프: 각 간선에 방향이 있되 양방향이지 않아야 한다.

 

 

---

 

  위상정렬을 구현하며 배운 것들

 

  최적화 전

// 입력
let input = require('fs').readFileSync(
	'/dev/stdin'
	).toString().trim().split('\n');


const queue = []

const answer = []

// 입력
const [N, M] = input[0].split(" ").map(Number)

// init node
const node = new Array(N + 1)

const indegree = new Array(N+1).fill(0)

for(let i = 0; i <= N+1; i++){
  node[i] = new Array()
}


for(let i = 1; i <= M; i++){
  const [A, B] = input[i].split(" ").map(Number)
  node[A].push(B)
  indegree[B] = indegree[B] + 1
}


function push(){
  indegree.forEach((el, index) => {
    
    if(el == 0){
      queue.push(index)
      indegree[index] = -1
    } 

  })
}

function shift(){
  const element = queue.shift()

  for(el of node[element]){
    indegree[el] = indegree[el] - 1
  }

  return element
}

indegree[0] = -1

push();


while(queue.length){
  const element = shift()
  
  answer.push(element)

  push()
}

const submit = answer.join(' ')
console.log(submit)

 

최적화 후

// 입력
let input = require('fs').readFileSync(
	'/dev/stdin'
	).toString().trim().split('\n');


const queue = []

const answer = []

// 입력
const [N, M] = input[0].split(" ").map(Number)

// init node
const node = new Array(N + 1)

const indegree = new Array(N+1).fill(0)

for(let i = 0; i <= N+1; i++){
  node[i] = new Array()
}


for(let i = 1; i <= M; i++){
  const [A, B] = input[i].split(" ").map(Number)
  node[A].push(B)
  indegree[B] = indegree[B] + 1
}


indegree[0] = -1

for(let i = 1; i <= indegree.length; i++){
  
  if(indegree[i] == 0){
    queue.push(i)
  }
}


while(queue.length){

  // shift
  const element = queue.shift()

  answer.push(element);

  for(el of node[element]){
    indegree[el] -= 1;
		// push
    if(indegree[el] == 0){
      queue.push(el);
    }
  }

}

const submit = answer.join(' ')
console.log(submit)

 

 

BOJ 2252(줄 세우기) 문제이다. 두 코드의 성능 차이가 확연하게 보인다.

(제출 시간의 간격은 약 15분 이지만, 실제로는 2일의 간격이 있다.)

 

 

가장 큰 원인은 원래 코드에서는 불필요한 반복문이 굉장히 많다는 점이다.

매 번 O(N)의 시간복잡도를 가진 for문을 사용하여 입력 데이터의 크기가 커질수록 비효율적이 된다.

 

생각해 보면, 위상 정렬은 한 노드에 방문했을 때 그 노드에 연결된 것들만 변경시킨다.

그 의미는 한 노드에 연결된 노드들만 변경시킨다는 얘기이다. 즉, 변경되지 않는 다른 노드는 확인할 필요가 없다.

이를 반영하여 원래는 진입차수만 변경하는 for of 문을 개조해서 변경하였다.

 

이렇게만 해주어도 최적화가 상당히 잘 된 것을 볼 수 있다.

 

---

 

  구현 방법

 

1. DFS를 활용한 구현
2. Queue를 활용한 구현

 

이 글에서는 Queue를 활용하여 구현을 해보았다.

 

1. 모든 노드의 진입 차수를 계산한다.(어떠한 노드에서 들어오는 간선의 수)

2. 진입 차수가 0인 노드를 큐에 넣는다.

3. 큐에서 노드를 꺼내 연결된 간선을 제거한다.

4. 진입 차수가 0이 된 노드들을 큐에 넣는다.

5. 3번과 4번을 반복한다.