[백준 1074] Z (Node.js) - 분할정복

문제 링크

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

1074번: Z

---

답안

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "text.txt";
const [n, r, c] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);

function solution(n, r, c) {
  let answer = 0;
  const divide = (row, col, size) => {
    if (row === r && col === c) {
      console.log(answer);
      return;
    }

    if (r >= row && r < row + size && c >= col && c < col + size) {
      let half = parseInt(size / 2);
      divide(row, col, half);
      divide(row, col + half, half);
      divide(row + half, col, half);
      divide(row + half, col + half, half);
    } else {
      answer += size * size;
    }
  };
  divide(0, 0, Math.pow(2, n));

  return answer;
}

solution(n, r, c);

 

해설

• 글로 표현하기가 상당히 어려운 것 같다.
• 프로그래밍이 실제 되는 것 처럼 직관적으로 분할정복의 흐름도를 그려보았다.

• row, col이 r, c과 같아질때까지 분할정복이 되는데
• Z 모양대로 순회한다는 것을 고려한 상태에서 코드를 작성해야 한다.
• Z 모양 순서는 재귀를 호출하는 순서가 될 것이다.