[백준] 1074

Z

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

풀이

const recurZ = (n, r, c) => {
  if (n === 0) return 0;
  let halfN = Math.pow(2, n - 1);
  if (r < halfN && c < halfN) return recurZ(n - 1, r, c);
  if (r < halfN && c >= halfN)
    return halfN * halfN + recurZ(n - 1, r, c - halfN);
  if (r >= halfN && c < halfN)
    return 2 * halfN * halfN + recurZ(n - 1, r - halfN, c);
  if (r >= halfN && c >= halfN)
    return 3 * halfN * halfN + recurZ(n - 1, r - halfN, c - halfN);
};

const z = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);
  console.log(recurZ(input[0], input[1], input[2]));
};

z();

반성회

1. 함수의 정의 : 2^n * 2^n 크기의 이차원 배열 내에 (r, c) 가 포함되는지 체크하고, 포함된다면 n이 0이 될 때까지 재귀를 반복하여 (r, c)를 몇 번째로 방문하는지 반환값을 더해가며 계산한다
2. 종료조건 : n이 0일 때 (r, c) 좌표에 도달했다는 의미이므로 (재귀는 r과 c가 2^n * 2^n 배열 내에 존재할 때만 진입한다) 0을 그대로 반환한다
3. 반환값 :
   1. n이 0일 때, 0 반환
   2. n이 0이 아닐 때, 배열을 2^(n - 1) * 2^(n - 1) 크기로 쪼개어 해당 범위 내에 (r, c) 좌표가 존재하는지 체크 (if 조건문 4개가 각각 4개의 하위 배열을 나타낸다)
      • 하위 배열의 크기가 halfN = 2^(n - 1) 이므로 4개의 조건문은 각각
        • r < halfN && c < halfN ⇒ 제4사분면, 길이 0부터 시작
        • r < halfN && c ≥ halfN ⇒ 제1사분면, 길이 halfN * halfN부터 시작 (제4사분면을 돌고 온 상태이므로)
        • r ≥ halfN && c < halfN ⇒ 제3사분면, 길이 2 * halfN * halfN부터 시작 (제4사분면, 제1사분면을 돌고 온 상태이므로)
        • r ≥ halfN && c ≥ halfN ⇒ 제2사분면, 길이 3 * halfN * halfN부터 시작 (제4사분면, 제1사분면, 제3사분면을 돌고 온 상태이므로)
      • (r, c) 좌표가 존재한다면 n = halfN인 재귀 다음단계로 진입하고, 위의 과정을 반복하여 길이를 잰다