x와 y좌표를 (0, 0)으로 시작해서 분할정복 함수를 호출한 다음 N/2만큼 더해줘서 4등분한 각 박스의 첫번째 인덱스를 가리킬 수 있도록 만들어줬다. matrix는 모두 -1로 할당되어 있어서 초기화상태로 있는 경우에만 누적되고 있는 cnt값을 할당해서 원하는 matrix(0~ 2^(n-1)이 저장된 배열)를 만들어주고 r행 c열의 값을 반환하려고 했다.

function solution(i) {
    const input = i.toString().trim().split(" ");
    [N, r, c] = input;
    N **= 2;
    let matrix = [...Array(N)].map(() => [...Array(N)].fill(-1));

    let cnt = -1;

    function qtree(N, x, y) {
        if (N > 1) {
            const div = Math.floor(N / 2);
            qtree(div, x, y);
            qtree(div, x, y + div);
            qtree(div, x + div, y);
            qtree(div, x + div, y + div);
        }
        if (matrix[x][y] === -1) matrix[x][y] = ++cnt;
    }
    qtree(N, 0, 0);
    console.log(matrix[r][c].toString());

    return matrix[r][c].toString();
}
JavaScript
복사

테스트를 돌려보니 아래의 3개 케이스가 너무 오래 걸려서 값이 출력되지 않았고 제출해보니 시간초과, 런타임에러( 스택 오버플로우)가 나왔다. 이럴 때는 재귀를 사용한 게 잘못된 것이라는 생각을 해야 하는데, 문제에 적혀있기로는 재귀 유형이라고 한다. 그럼 에지 케이스 처리를 잘하거나 메모이제이션?을 해야할 것 같다.

맞는 풀이

그래서 찾아보니 값을 누적하면 재귀를 타고 들어가는 횟수를 획기적으로 줄일 수 있는 방법을 찾아서 적용해야 하는 것 같았다.

그 방법은 아래와 같았다. 좌표 (x, y)와 N이라는 범위가 quadTree 함수 내에서 주어지니 타고 들어간 행렬의 x좌표의 범위와 y좌표의 범위 내에 r과 c가 존재하는지 확인할 수 있는 것이다.

만약 존재하지 않는다면 아래의 조건문에서 결과값 res에 행렬의 크기 N*N을 누적해놓는다.(나중에 r행 c열을 찾게 되면 이때 방문하지 않았던 행렬은 방문한 것처럼 값이 누적된 상태다.)

// & : 원하는 좌표가 포함되는 행렬이 아닐 때 해당 범위의 값을 그 행렬의 크기로 계산해서 누적해주면 된다.
if (!(x <= r && r < x + N && y <= c && c < y + N)) {
    res += N * N;
    return;
}
JavaScript
복사

위의 조건문에 걸리지 않으면 재귀를 타고 들어갔을 때 항상 수행해야 하는 로직이 있다.

N을 2로 나누어 4등분한 각각의 행렬로 타고 들어가는 것이다. 이때 만약 r행 c열이라면 그 값이 answer가 된다.

function quadTree(N, x, y) {
        if (x == r && y == c) {
            answer = res.toString();
            return;
        }
        // & : 원하는 좌표가 포함되는 행렬이 아닐 때 해당 범위의 값을 그 행렬의 크기로 계산해서 누적해주면 된다.
        if (!(x <= r && r < x + N && y <= c && c < y + N)) {
            res += N * N;
            return;
        }

        const div = Math.floor(N / 2);
        quadTree(div, x, y);
        quadTree(div, x, y + div);
        quadTree(div, x + div, y);
        quadTree(div, x + div, y + div);
    }
JavaScript
복사

소스코드

function solution(i) {
    const input = i.toString().trim().split(" ");
    [N, r, c] = input;
    let res = 0;

    function quadTree(N, x, y) {
        if (x == r && y == c) {
            answer = res.toString();
            return;
        }
        // & : 원하는 좌표가 포함되는 행렬이 아닐 때 해당 범위의 값을 그 행렬의 크기로 계산해서 누적해주면 된다.
        if (!(x <= r && r < x + N && y <= c && c < y + N)) {
            res += N * N;
            return;
        }

        const div = Math.floor(N / 2);
        quadTree(div, x, y);
        quadTree(div, x, y + div);
        quadTree(div, x + div, y);
        quadTree(div, x + div, y + div);
    }
    quadTree(2 ** N, 0, 0);

    return answer;
}

test("solution", () => {
    expect(solution(`2 3 1`)).toStrictEqual("11");
    expect(solution(`3 7 7`)).toStrictEqual("63");
    expect(solution(`1 0 0`)).toStrictEqual("0");
    expect(solution(`4 7 7`)).toStrictEqual("63");
    expect(solution(`10 511 511`)).toStrictEqual("262143");
    expect(solution(`10 512 512`)).toStrictEqual("786432");
});
JavaScript
복사