위상 정렬 (Topological Sort)

정의

• 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위해하지 않도록 나열하는 정렬이다.
  • 예를 들어 A에서 C로 가는 간선이 있으면 위상 정렬을 했을 때 A는 C보다 앞에 등장해야 된다.
• 만일 그래프 내에 사이클이 존재할 경우 올바른 위상 정렬이 존재 할 수가 없다.
  • 예를 들어 A -> B -> C의 간선이 있을 경우 순환이 되기 때문에 선후관계에 모순이 발생하게 된다.
    그렇기에 사이클이 존재하지 않아야 위상 정렬이 가능하다.

구현

1. 맨 처음 간선들을 읽으며 indegree 배열을 채운다.
2. indegree가 0인 정점들을 모두 큐에 넣는다.
3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가
4. 해당 정점으로부터 연결된 모든 정점의 indegree값을 1 감소시킨다. 이 때 indegree가 0이 될 경우 그 정점을 큐에 넣는다.
5. 큐가 빌 때까지 3,4번을 반복한다.

구현 예시

예시 그래프

1. 첫 indegree배열에 간선이 0일 경우의 모든 정점을 큐에 넣는다.
   

2. 큐에 첫 원소인 A에서 출발한 정점의 indegree배열의 값을 1감소 해준다. 그리고, 큐에서 나와 위상 정렬 결과에 출력한다.

3. 다시 큐에서 나온 값 C에 연결된 정점의 indegree값을 1씩 감소 시켜준다. 여기서 D의 값이 0이 됨으로 D의 값을 큐에 넣어준다.

4. G와 연결된 E의 값을 1 감소

5. D와 연결된 B,E의 값을 1씩 빼고 연결된 B,E의 값은 0이 됨으로 큐에 넣어준다.

6. B출력

7. E에 연결된 F의 값을 1줄이고 F를 큐에 넣는다.

8. F를 끝으로 다 출력하면 아래와 같은 결과가 나온다.
   

위상 정렬 문제 (백준_줄 세우기)

문제

N명의 학생들을 키 순서대로 줄을 세우기 위해, 일부 학생들의 키를 비교한 결과를 주어졌을 때 줄을 세우는 프로그램을 작성하시오.

• Input:
  • 첫 줄: 학생 수 N (1 <= N <= 32,000), 비교한 수 M (1 <= N <= 100,000)
  • 나머지: A와 B 번호를 가진 학생이고, A가 B보다 앞에 서야 한다.

3 2
1 3
2 3

• Output:

1 2 3

문제 풀이

const fs = require("fs");
const input = fs
  .readFileSync("dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.split(" "));
const shift = input.shift().map(Number); // [N,M]
// 정점에서 출발한 간선들을 담아 놓을 배열 (ex: A -> B = [B])
let indegree = Array.from({ length: shift[0] }, () => []); 
// 정점의 갯수 만큼 연결된 간선 개수의 배열을 만들어준다.
let countArr = Array(Number(shift[0])).fill(0); // 
let ans = [];

function answersort() {
  let quene = [];
  // 처음 부터 countArr의 원소가 0일 경우, quene에 넣어준다.
  countArr.map((item, idx) => { 
    return item === 0 ? quene.push(idx + 1) : null;
  });
  // quene가 0일 경우, 위상정렬이 불가하거나, 위상정렬이 끝난 경우 
  while (quene.length) {
    let zero = quene.shift(); // 큐에서 나온 정점
    // zero에서 출발한 간선의 값을 줄여주고 만일 도착지점의 정점이 0일 경우 quene에 넣어준다.
    indegree[zero - 1].forEach((item) => { 
      countArr[item - 1]--;
      countArr[item - 1] === 0 ? quene.push(item) : null;
    });
    ans.push(zero);
  }
}

for (let i = 0; i < input.length; i++) {
	//출발한 정점, 연결된 정점들을 각 배열들에 연결
  indegree[Number(input[i][0]) - 1].push(Number(input[i][1]));
  countArr[Number(input[i][1]) - 1]++;
}

answersort();

console.log(ans.join(" "));

);

참고 링크
https://blog.encrypted.gg/1020 (바킹톡 - 위상정렬)