[JS] 백준 2252번 : 줄세우기 - 그래프이론, 위상정렬, 큐

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

 

이전에 포스팅했던 위상정렬의 문제다

https://ydoag2003.tistory.com/43

위상 정렬

 

 

📋풀이방법

1. 연결되어있음을 표현할 graph배열과 간선의 정보를 표현할 indegrees배열을 선언한다

 -graph배열은 인덱스를 기준으로 연결되어있는 값을 그 안에 누적한다.

 ex) graph[1]에 [3,4]가 들어있다면 1 - 3, 1 - 4 와 같이 연결되어있음

 -indegrees배열은 인덱스를 기준으로 연결되어있는 값의 갯수를 뜻함

 ex)위 예시를 기준으로 indegress[1]에는 2가 들어있다.

2. 주어진 학생의 번호 A와 B를 graph[a]에 B값을 누적한다.

 ->graph[A]에 넣는 이유는 A가 키가 작으므로 앞에 오니까 queue를 이용할 때 앞에서 부터 값을 빼므로 graph[A]에 B값을 넣는다.

3. 학생의 A와 B의 비교 값을 graph에 기록하면서 indegress[B] 값을 +1해준다.

 -> A가아닌  indegress[B] 값을 +1하는 이유는 위상정렬은 진입차수가 0인 것을 기준으로 풀이하므로 [ 1 - 3 ]에서 3에 진입차수가 +1된것이다. 그래야 위에서 말했듯이 작은 키 순서대로 출력이된다.

4. 모든 정보를 기록하고 indegress의 값이 0인 인덱스를 찾아서 queue에 넣어준다

->진입차수가 0인 인덱스들이 순서가 먼저임을 뜻하므로 queue에 넣어준다.

5.queue에서 하나씩 빼면서 뺀 인덱스 값은 정답에 기록한다

6. queue에서 뺀 인덱스에 연결된 노드들을 순회한다.

7. 그 노드들의 연결된 간선을 제거한다. ->진입차수를 빼줌

8. 제거하면서 만약 제거된 노드의 indegrees값이 0이 됐다면 queue에 그 노드를 넣어준다.

9. 넣어준 노드는 다음 순서가 된다.

10. 이를 queue가 빌 때까지 반복한다.

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let [N, M] = input[0].split(" ").map(Number);
let arr = [];
let queue = [];
let answer = [];
for (var i = 0; i < M; i++) {
  arr[i] = input[i + 1].split(" ").map(Number);
}

const graph = Array.from({ length: N + 1 }, () => Array().fill(0));
const indegrees = Array(N + 1).fill(0);

for (let i = 0; i < M; i++) {
  let [a, b] = arr[i];
  graph[a].push(b);
  indegrees[b]++;
}

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

while (queue.length) {
  let x = queue.shift();
  answer.push(x);
  for (let next of graph[x]) {
    indegrees[next]--;
    if (indegrees[next] == 0) queue.push(next);
  }
}

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