[노드JS/알고리즘] 백준 - 1074번 Z

[문제]

1074번: Z

 

[코드]

let [N, r, c] = (
  process.platform === "linux"
    ? require("fs").readFileSync("/dev/stdin").toString().trim()
    : `4 7 7`
)
  .trim()
  .split(" ")
  .map((v) => +v);

let res = 0;
const divide = (row, col, size) => {
  if (row === r && col === c) {
    // 좌표 찾음
    console.log(res);
    return;
  }
  if (r >= row && r < row + size && c >= col && c < col + size) {
    // 영역 내에 있음
    size = parseInt(size / 2);
    divide(row, col, size);
    divide(row, col + size, size);
    divide(row + size, col, size);
    divide(row + size, col + size, size);
  } else res += size * size; // 좌표 못 찾음!
};

divide(0, 0, Math.pow(2, N));

 

• divide 함수를 만들어 분할정복한다.
  • 주어진 r, c가 재귀적으로 주어지는 row, col과 같다면 정답 처리.
  • 만약, r과 c가 영역 내에 있다면 분할하여 탐색한다.
    • 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서대로 방문. (Z 형태)
  • 영역 밖에 있다면, 해당 영역의 크기만큼 res에 더해준다. (해당 영역의 크기만큼 스킵)

 

---

• 문제 풀기 전, 시간 제한이 0.5초, 추가 시간이 없다는걸 보고 주의 해야겠다고 생각했다.
• 어떻게하면 효율적으로 분할할 수 있을지 고민했지만, 답은 쉽게 나오지 않았고 결국 다른 글을 참고 했다.
  • 로직은 얼추 비슷했지만, 해당 영역에서 좌표를 포함하고 있지 않을 때, 건너뛰는 걸 고려하지 않았었다!!