백준 1074번 Z (javascript)

우선 재귀 문제를 풀 때 가장 중요한 부분은 `예시 분석`이라고 생각한다. 재귀가 살짝 머리가 아픈 개념이기 때문에, 구현을 하기 위해서는 코드를 어떻게 구현할건지 그 아이디어가 머릿속에 정리가 돼있어야 한다.

따라서, 먼저 테스트 케이스 1번을 분석하여 문제의 흐름을 파악한 뒤에 이를 토대로 구현해보자.

예제 분석

우선 나는 처음에 주어진 행열(3,1)을 찾기 위해 전체 배열을 4개의 사분면으로 나누는 방식으로 접근했다. 한 번 분할할 때마다 사분면의 크기는 배열 size /2가 된다.

첫 번째 분할

주어진 배열의 크기가 $$ 2^N x 2^{N} $$이므로, N = 2일 때 배열은 4 x 4이다. 이 배열을 4개의 사분면으로 나누면 각 사분면은 2 x 2 크기가 되고 각 사분면에는 아래의 숫자들이 포함된다.

• 0사분면 (왼쪽 위): 숫자 0, 1, 2, 3
• 1사분면 (오른쪽 위): 숫자 4, 5, 6, 7
• 2사분면 (왼쪽 아래): 숫자 8, 9, 10, 11
• 3사분면 (오른쪽 아래): 숫자 12, 13, 14, 15

찾고자 하는 좌표 (3, 1)은 2사분면에 위치한다. 따라서 0사분면과 1사분면의 숫자들을 모두 건너뛰고, 2사분면부터 탐색하면 된다. 여기서 0사분면과 1사분면의 숫자는 각각 4개씩 있으므로, 총 8개의 숫자를 넘어간다.

두 번째 분할

이제 2사분면을 다시 4개의 작은 사분면으로 나눈다. 나눠진 각 사분면의 크기는 1 x 1이 된다. 더 이상 배열로 나눌 수 없고, 각 칸이 하나의 숫자를 나타내게 된다.

• 0사분면 (왼쪽 위): 숫자 8
• 1사분면 (오른쪽 위): 숫자 9
• 2사분면 (왼쪽 아래): 숫자 10
• 3사분면 (오른쪽 아래): 숫자 11

여기서 좌표 (3,1)은 3사분면에 위치하므로, 0사분면, 1사분면, 2사분면에 있는 모든 숫자를 건너뛴 다음에 오게 된다. 즉, 총 3개의 숫자를 건너뛰면 된다. 앞에서 계산했던 숫자 8에 3을 더하게 되면 11이므로, (3,1)에 존재하는 숫자는 11번째로 방문하는 숫자 11이 된다.

이걸 코드로 표현하면 아래와 같다.

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ');

let N = +input[0];
let targetRow = +input[1];
let targetCol = +input[2];

function visitZ(r, c, size, num) {

    if(r === targetRow && c === targetCol) return num;

    size /= 2;

    //사분면 계산
    let quadrant = 0;
    if(r + size <= targetRow) quadrant += 2;
    if(c + size <= targetCol) quadrant += 1;

    num += size * size * quadrant;

    switch(quadrant) {
        case 0:
            return visitZ(r, c, size, num);
        case 1:
            return visitZ(r, c + size, size, num);
        case 2:
            return visitZ(r + size, c, size, num);
        case 3: 
            return visitZ(r + size, c + size, size, num);
    }
}

console.log(visitZ(0, 0, 2 ** N, 0));