문제 개요

문제: 사분면

분류: 수학, 분할 정복

난이도: 골드4

문제 풀이

사분면 조각 번호의 자릿수 d가 주어질 때 좌표평면을 2^d 크기의 행렬로 가정하고 문제를 풀이한다.

1. 2^d 행렬 내에서 사분면 조각의 좌표를 구한다.
2. 구한 좌표에서 주어진 이동 횟수만큼 이동했을 때의 좌표를 구한다.
3. 이동한 좌표가 좌표평면(=행렬) 위를 벗어났다면 -1을 출력하고,
   그렇지 않다면 이동한 좌표에 해당하는 사분면 조각 번호를 찾아 출력한다.

위 과정에서 사분면 조각의 좌표와 이동한 좌표에 해당하는 사분면 조각 번호를 찾기 위해서 재귀 함수를 사용한다.

• 제1사분면 → (r, c+size/2)에서 재탐색
• 제2사분면 → (r, c)에서 재탐색
• 제3사분면 → (r+size/2, c)에서 재탐색
• 제4사분면 → (r+size/2, c+size/2)에서 재탐색

예를 들어 문제의 예제 입력1처럼 341번 조각의 좌표를 구한다고 해보자.

전체 행렬의 크기를 size, 현재 좌표를 (r,c)라고 했을 때 341의 자릿수가 3이므로 size는 8이 되며 처음 좌표는 (0, 0)에서 시작한다.

341은 먼저 제3사분면(”3”41)에 해당하므로 (r+size/2, c)인 (4, 0)으로 이동한 후 다시 탐색을 진행한다. 이때 size는 절반으로 줄어 4가 된다.
즉, (4, 0)에서 시작하는 4x4 행렬에서 재탐색한다.

4x4 행렬에서 341은 제4사분면(3”4”1)에 해당하므로 (r+size/2, c+size/2)인 (6, 2)로 이동하고 size는 2로 줄어든다.

마지막으로 2x2 행렬에서는 제1사분면(34”1”)에 해당하기 때문에 (r, c+size/2)인 (6, 3)으로 이동하고 size는 1로 줄어든다.

size가 1인 1x1 행렬에서는 더이상 탐색할 수 없으므로 현재 좌표인 [6, 3]을 반환한다.

이 상태에서 좌표를 이동시킨 후 이동한 좌표의 사분면 조각 번호를 찾는 것 또한 위 과정과 비슷한 방법으로 진행하면 된다.

코드

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

const getInitCoord = (str, idx, r, c, size) => {
  if (size === 1) return [r, c];

  if (str[idx] === "1")
    return getInitCoord(str, idx + 1, r, c + size / 2, size / 2);
  if (str[idx] === "2") return getInitCoord(str, idx + 1, r, c, size / 2);
  if (str[idx] === "3")
    return getInitCoord(str, idx + 1, r + size / 2, c, size / 2);
  else return getInitCoord(str, idx + 1, r + size / 2, c + size / 2, size / 2);
};

const getDestQuad = (y, x, r, c, size) => {
  if (size === 1) return "";

  if (y < r + size / 2 && x >= c + size / 2)
    return "1" + getDestQuad(y, x, r, c + size / 2, size / 2);
  if (y < r + size / 2 && x < c + size / 2)
    return "2" + getDestQuad(y, x, r, c, size / 2);
  if (y >= r + size / 2 && x < c + size / 2)
    return "3" + getDestQuad(y, x, r + size / 2, c, size / 2);
  else return "4" + getDestQuad(y, x, r + size / 2, c + size / 2, size / 2);
};

const solution = (input) => {
  const [d, num] = input[0].split(" ");
  const [moveX, moveY] = input[1].split(" ").map(Number);

  // 좌표평면을 2^d 크기의 행렬로 가정하고 풀이한다.
  const size = 2 ** +d;

  // 행렬 내에서 주어진 사분면 조각의 좌표를 구한다.
  let [y, x] = getInitCoord(num, 0, 0, 0, size);

  // 주어진 이동 횟수대로 이동했을 때의 좌표를 구한다.
  // 이때 moveY는 위쪽으로 이동한 경우 양수, 아래쪽으로 이동한 경우 음수로 주어진다.
  // 행렬에서는 위쪽으로 이동한 경우 음수, 아래쪽으로 이동한 경우 양수이다.
  // 즉 반대이므로 moveY는 y에서 뺄셈해야 한다.
  y -= moveY;
  x += moveX;

  // 이동했을 때 좌표평면(=행렬)을 벗어난다면 -1을 출력하고
  // 그렇지 않다면 이동한 좌표에 해당하는 사분면 조각의 번호를 찾아 출력한다.
  if (y < 0 || y >= size || x < 0 || x >= size) console.log(-1);
  else console.log(getDestQuad(y, x, 0, 0, size));
};

solution(input);