오늘은 위상 정렬에 대해 알아보겠습니다.
⭐️ 위상 정렬(Topological Sort)이란 ?
Topological 에서의 Topology는 그리스어에서 위치를 뜻하는 topos와 학문을 뜻하는 logos로 만들어진 단어입니다.위상 정렬이란 순환하지 않는 유향 그래프를 방향성에 거스르지 않도록 순서대로 정렬하는 방법입니다. (뭔소리..)
예시를 한 번 들어보겠습니다.
예를 들어 , A가 등교하는 방법에 대해 생각을 해보겠습니다.
자차를 가진 A는 차를 직접 운전해서 가거나 , 대중 교통을 이용하여 등교를해야 합니다.
차를 타고 등교를 하는 방법에는 ,
시동을 건다 -> 톨 게이트를 지나친다 -> 학교에 도착한다 -> 학교 주차장에 주차한다 -> 교실에 들어간다
대중교통을 탄다면 ,
1. 지하철을 탔을 때 : 교통 카드를 찍는다 -> 학교 지하철 역에서 내린다 -> 학교에 도착한다 -> 교실에 들어간다
2. 버스를 탔을 때 : 교통 카드를 찍는다 -> 학교 버스 정류장에서 내린다 -> 학교에 도착한다 -> 교실에 들어간다
와 같은 과정이 있을 것입니다. 앞서의 과정을 보면 학교에 도착하려면 자차를 타든 대중 교통을 타든 되어야 하는 선행 과정들이 존재합니다. 위에서 말한 방향성이란 이런 선행 과정들을 뜻하는 것이고 , 순환하지 않는다는 것(Cycle 존재 X)은 한 과정이 반복(시동을 계속 건다 등 .. ) 되지 않는 그래프일 때 , 위상 정렬을 적용할 수 있다는 이야기입니다.
경우의 수가 여러 개 생길 수 있기 때문에 하나의 그래프에 대해서 여러 가지의 정렬 값이 존재할 수 있습니다.
위상 정렬을 이해하기 위해선 진입 차수와 진출 차수에 대해 알아야 합니다.
진입차수: 어떤 노드 N으로 향하는 간선의 개수
진출차수: 어떤 노드 N에서 다른 노드로 향하는 간선의 개수
⭐️ 구현 백준 1766 : 문제집
실제 코드의 구현과 접근 방식은 예시를 들어 설명하도록 하겠습니다.
문제에 대한 해석을 해보자면 , 입력 값은 Node 4-> Node 2 와 같이 노드와 노드 간의 관계를 방향성을 제시하여 나타내고 있습니다. 4가 선행 학습이 되어야 2를 학습한다라는 뜻이겠죠 ? 또한 , 다른 조건으로는 숫자 값이 작을 수록 우선수 과목으로 취급하고 있습니다.
문제를 풀기 위해서는
1. 입력값을 토대로 한 방향성 그래프를 만든다. (진출 차수를 토대로)
2. 각 노드에 대한 진입 차수 배열을 만든다.
const [n, m] = input[0];
const arr = input.slice(1);
const graph = Array.from({ length: n + 1 }, () => []);
const inDegree = Array.from({ length: n + 1 }, () => 0);
for (let rel of arr) {
const [a, b] = rel;
// 진출 차수 기반 graph
graph[a].push(b);
// 노드 별 진입 차수
inDegree[b]++;
}앞서 진입 차수와 진출 차수를 먼저 설명한 이유는 진입 차수 배열을 만들어야 하기 때문입니다. 진입 차수가 0이라는 것은 선행을 필요로 하는 과목(노드)이 없다라는 뜻이기 때문에 , 가장 먼저 실행돼도 상관없다는 것을 의미합니다.
- 진입 차수가 0인 노드와 연결된 노드를 Queue에 담는다 (Khan 알고리즘) or DFS를 통해 진입 차수가 0인 노드의 줄기를 전부 탐색한다.
두 알고리즘 모두 진입차수가 0인 노드를 엣지와 함께 순서대로 제거하는 방식으로 이루어집니다. 순환하지 않는 유향 그래프가 진입차수가 0인 노드를 반드시 하나 이상 포함한다는 사실은 증명되어 있기 때문에 두 알고리즘을 모두 사용이 가능한 것입니다. 두 알고리즘 모두 O(V+E)의 시간 복잡도를 지닙니다.
해당 문제는 Khan 알고리즘을 이용하여 구현해보도록 하겠습니다.
위 문제는 숫자 값이 작을 수록 우선수 과목으로 취하고 있기 때문에 MinHeap을 통해 구현해보도록 하겠습니다. 힙과 우선 순위 큐에 대하여
class MinHeap {
constructor() {
this.heap = [];
}
getLength() {
return this.heap.length;
}
getLeftChildIdx(idx) {
return 2 * idx + 1;
}
getRightChildIdx(idx) {
return 2 * idx + 2;
}
getParentIdx(idx) {
return Math.floor((idx - 1) / 2);
}
insert(value) {
this.heap.push(value);
this.heapifyUp();
}
heapifyUp() {
let index = this.heap.length - 1;
const lastInsertedNode = this.heap[index];
while (index > 0) {
const parentIdx = this.getParentIdx(index);
if (this.heap[parentIdx] > lastInsertedNode) {
this.heap[index] = this.heap[parentIdx];
index = parentIdx;
} else break;
}
this.heap[index] = lastInsertedNode;
}
remove() {
if (this.heap.length === 0) return null;
const rootNode = this.heap[0];
if (this.heap.length === 1) this.heap = [];
else {
this.heap[0] = this.heap.pop();
this.heapifyDown();
}
return rootNode;
}
heapifyDown() {
let index = 0;
const count = this.heap.length;
const rootNode = this.heap[0];
while (this.getLeftChildIdx(index) < count) {
const leftChildIdx = this.getLeftChildIdx(index);
const rightChildIdx = this.getRightChildIdx(index);
const smallerIdx =
rightChildIdx < count &&
this.heap[rightChildIdx] < this.heap[leftChildIdx]
? rightChildIdx
: leftChildIdx;
if (this.heap[smallerIdx] <= rootNode) {
this.heap[index] = this.heap[smallerIdx];
index = smallerIdx;
} else break;
}
this.heap[index] = rootNode;
}
}- 진입 차수가 0인 노드가 진출하고 있는 노드(연결된)들을 탐색하며 , 해당하는 노드의 진입 차수를 감소 시켜줍니다. 그 과정에서 진입 차수가 0(모든 선행 과목 이수)이 되면 pq에 삽입하여 줍니다.
- 이 과정들을 반복하여 pq가 빌 때까지 (모든 노드의 진입 차수를 0으로 만들었을 때) 수행해줍니다.
const pq = new MinHeap();
const result = [];
for (let i = 1; i < inDegree.length; i++) {
const count = inDegree[i];
if (count === 0) {
pq.insert(i);
}
}
while (pq.getLength()) {
const cur = pq.remove();
result.push(cur);
for (const node of graph[cur]) {
--inDegree[node];
if (inDegree[node] === 0) {
pq.insert(node);
}
}
}⭐️ 전체 코드
class MinHeap {
constructor() {
this.heap = [];
}
getLength() {
return this.heap.length;
}
getLeftChildIdx(idx) {
return 2 * idx + 1;
}
getRightChildIdx(idx) {
return 2 * idx + 2;
}
getParentIdx(idx) {
return Math.floor((idx - 1) / 2);
}
insert(value) {
this.heap.push(value);
this.heapifyUp();
}
heapifyUp() {
let index = this.heap.length - 1;
const lastInsertedNode = this.heap[index];
while (index > 0) {
const parentIdx = this.getParentIdx(index);
if (this.heap[parentIdx] > lastInsertedNode) {
this.heap[index] = this.heap[parentIdx];
index = parentIdx;
} else break;
}
this.heap[index] = lastInsertedNode;
}
remove() {
if (this.heap.length === 0) return null;
const rootNode = this.heap[0];
if (this.heap.length === 1) this.heap = [];
else {
this.heap[0] = this.heap.pop();
this.heapifyDown();
}
return rootNode;
}
heapifyDown() {
let index = 0;
const count = this.heap.length;
const rootNode = this.heap[0];
while (this.getLeftChildIdx(index) < count) {
const leftChildIdx = this.getLeftChildIdx(index);
const rightChildIdx = this.getRightChildIdx(index);
const smallerIdx =
rightChildIdx < count &&
this.heap[rightChildIdx] < this.heap[leftChildIdx]
? rightChildIdx
: leftChildIdx;
if (this.heap[smallerIdx] <= rootNode) {
this.heap[index] = this.heap[smallerIdx];
index = smallerIdx;
} else break;
}
this.heap[index] = rootNode;
}
}
function solution(input) {
/** 문제의 수 : n, 정보의 개수 : m */
const [n, m] = input[0];
const arr = input.slice(1);
const graph = Array.from({ length: n + 1 }, () => []);
const inDegree = Array.from({ length: n + 1 }, () => 0);
for (let rel of arr) {
const [a, b] = rel;
// 진출 차수 기반 graph
graph[a].push(b);
// 노드 별 진입 차수
inDegree[b]++;
}
const pq = new MinHeap();
const result = [];
// 진입 차수가 0인 노드들을 pq에 넣음
for (let i = 1; i < inDegree.length; i++) {
const count = inDegree[i];
if (count === 0) {
pq.insert(i);
}
}
while (pq.getLength()) {
const cur = pq.remove();
// 진출 차수가 0인 노드들만 pq에 담기므로 방문했다는 결과 표시
result.push(cur);
// 진입 차수가 0인 노드가 향하는 노드들 탐색하고 수행했다는 표시로 진입 차수 1 감소
for (const node of graph[cur]) {
--inDegree[node];
if (inDegree[node] === 0) {
pq.insert(node);
}
}
}
console.log(result.join(" "));
}
const rl = require("readline").createInterface({
input: process.stdin,
output: process.stdout,
});
const input = [];
rl.on("line", (line) => {
input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", () => {
solution(input);
process.exit();
});
