백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 2252 , 줄 세우기 [위상 정렬]

백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 2252 , 줄 세우기 [위상 정렬]

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

문제 출처 🏠

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

2252번: 줄 세우기

 

 

 

문제풀이 소감 🧑‍💻

위상 정렬을 처음 적용해본 문제였다. 처음에 동일한 자식에 대한 부모를 어떻게 구분할 것인지에 많은 고민이 필요했는데,

그럴 필요없이 queue 를 사용해서 동차 순위에 있는 값들을 모두 넣어주고 각 자식들에 우선순위를 조절해나아가면서 푸는 방법이 되게 신기했다. 이 문제는 정답이 여러개이므로 해당 풀이 말고도 다른 풀이로도 충분히 풀 수 있을 것같다.

 

 

 

요구사항 📋

첫째줄에 N,M이 주어짐. (N: 학생수, M: 키 비교 횟수)
M개의 키비교가 주어짐. (A,B)
A는 B의 앞에 서야함.
모든 키비교를 입력받고 학생들을 세운 결과를 출력하시오.
답이 여러가지인 경우 아무거나 출력.

 

 

해결 전략 📝

앞쪽에 있는 사람을 뒤쪽에 있는 사람의 부모로 설정한다.
또한, 우선순위를 rank 라는 배열에 저장하면서 각 사람의 우선순위를 부여한다.
뒤쪽에 여러번 나올수록 후순위로 밀리게된다.

모든 입력을 받고도 아직 우선순위가 0이라면 루트노드에 위치한 것이므로
이 값들을 queue에 넣어준다. 루트노드부터 차례대로 내려가면서 각 순위에 맞게 결과값을 더해나아가자.

 

 

 

 

기능 목록 📲

 

let lineOrder = Array.from({ length: N + 1 }, () => []);
let rank = Array.from({ length: N + 1 }, () => 0);
let deque = [];
let result = [];
Case.forEach((info) => {
    const [front, back] = info;
    rank[back] += 1;
    lineOrder[front].push(back);
});

 

1. 입력에 맞게 각 학생의 우선순위를 부여한다. 

 

lineOrder => 자식 노드에 대한 정보를 저장한다.

rank  => 각 학생의 우선순위 정보를 저장한다.

 

Case 를 다 순회하고도 rank 값이 0으로 남아있다면, 그 학생들이 루트에 위치한 학생이다.

 

 

2. 루트인 학생 정보를 queue에 저장한다.

 

rank.forEach((ranking, idx) => {
    if (ranking === 0) {
      deque.push(idx);
      result.push(idx);
    }
});

 

이때, 루트에 있는 학생들은 맨앞쪽에 줄을 서줘야하므로 result에 차례로 push 한다.

 

참고로, 이 과정에서 0번 rank 인 학생들의 순서는 상관없다.

 

 

 

3. queue 를 돌면서 각자의 자식 노드에 대한 우선순위를 땡겨준다. 

 

while (deque.length !== 0) {
    nowStudent = deque.shift();
    for (const student of lineOrder[nowStudent]) {
      rank[student] -= 1;
      if (rank[student] === 0) {
        result.push(student);
        deque.push(student);
      }
    }
  }

 

자식노드로 거쳐가면서 각 자식의 우선순위를 -1 해준다.

 

만약, 자식의 우선순위가 0이 된다면, 줄에 세울 차례이므로 결과값에 넣어주고, 해당 학생노드의 자식들도 이어서 확인해야하기때문에 queue에 담아준다.

 

 

더이상 queue에 담긴 값이 없다면 더이상 확인할 값이 없으므로 종료한다.

 

 

 

정답 💯

 

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const [input_N, input_M] = input[0];
input.shift();
const input_Case = input;
function solution(N, M, Case) {
  let lineOrder = Array.from({ length: N + 1 }, () => []);
  let rank = Array.from({ length: N + 1 }, () => 0);
  let deque = [];
  let result = [];
  Case.forEach((info) => {
    const [front, back] = info;
    rank[back] += 1;
    lineOrder[front].push(back);
  });
  rank.forEach((ranking, idx) => {
    if (ranking === 0) {
      deque.push(idx);
      result.push(idx);
    }
  });
  while (deque.length !== 0) {
    nowStudent = deque.shift();
    for (const student of lineOrder[nowStudent]) {
      rank[student] -= 1;
      if (rank[student] === 0) {
        result.push(student);
        deque.push(student);
      }
    }
  }
  const answer = result.splice(1).join(" ");
  return answer;
}

console.log(solution(input_N, input_M, input_Case));