[백준] 골드V : 1074번 Z

🔎 문제

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

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

다음 예는 $2^{2}⨉2^{2}$  크기의 배열을 방문한 순서이다.

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

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

🔎 입력

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

🔎 출력

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

🔎 제한

• $1 ≤ N ≤ 15$
• $0 ≤ r, c < 2^N$

---

✅ 예제 1

입력

2 3 1

출력

11

✅ 예제 2

입력

3 7 7

출력

63

 

---

📌 C++ 구현 코드

#include <iostream>

using namespace std;

void fillMatrix(int n, int startRow, int startCol, int startNum, int row, int col)
{
    if (n == 1)
    {
        int num = startNum;
        for (int i = startRow; i < startRow + 2; i++)
        {
            for (int j = startCol; j < startCol + 2; j++)
            {
                if (i == row && j == col)
                {
                    cout << num;
                    return;
                }
                num++;
            }
        }
        return;
    }

    int size = (1 << (n - 1));
    int box = size * size;

    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            if (startRow + i * size <= row && row < startRow + (i + 1) * size && startCol + j * size <= col && col < startCol + (j + 1) * size)
            {
                fillMatrix(n - 1, startRow + i * size, startCol + j * size, startNum + box * (2 * i + j), row, col);
            }
        }
    }

    return;
}

int main()
{
    int n, r, c;
    cin >> n >> r >> c;

    fillMatrix(n, 0, 0, 0, r, c);

    return 0;
}