백준 20364 < 부동산 다툼 > JavaScript

📍문제 링크

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

20364번: 부동산 다툼

 

📍알고리즘 분류

- 트리

 

📍문제 풀이

- 왼쪽 자식 노드가 부모 노드 * 2

- 오른쪽 자식 노드가 부모 노드 * 2 + 1

이상의 규칙을 만족하는 트리를 만들고, 노드 번호가 적힌 배열을 순회하며 dfs를 진행하는 방법을 떠올렸지만,

노드의 갯수가 2^20 개가 될 수 있기 때문에 시간초과가 발생할 것이다.

 

따라서 전체 트리 탐색은 1번만 실행해야  한다.

 

대신 노드 번호가 적힌 배열을 순회하며, 해당 노드에서 루트(1번 노드)까지 가는데, 도중에 이미 탐색을 실시한 노드 번호를 마주치는지를 확인하면 된다.

 

📍코드 (JavaScript)

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [vertexNum, duckNum] = in1.split(" ").map(Number);
const targetArr = in2.map(Number);
const answer = Array(duckNum).fill(0);
const isOpen = Array(vertexNum + 1).fill(true);

for (let i = 0; i < duckNum; i++) {
  let current = targetArr[i];

  while (current !== 1) {
    if (!isOpen[current]) {
      answer[i] = current;
    }
    current = Math.floor(current / 2);
  }
  if (answer[i] === 0) isOpen[targetArr[i]] = false;
}

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

 

📍리뷰

- 주의할 점은, 처음, 이미 점유된 노드를 마주쳤을 때, while 문을 break하면 안된다.

원래 문제는 루트 노드에서 시작하여 처음 만난 점유된 노드 번호를 출력하는 것이기 때문에, 밑에서 거슬러 올라올 때는, 루트까지 가면서 마주친 점유된 노드 번호를 업데이트 해줘야 한다.

 

그래야 루트에서 내려가면서 처음 마주친 노드를 기록할 수 있다