[백준][BOJ][C++][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열을 몇 번째로 방문했는지 출력한다.

코드

이 문제는 계속 틀려 꾸준한 님의 블로그에서 코드를 보았지만 아직 모르겠습니다.

꾸준한님의 블로그 주소와 코드 공유 드리겠습니다.

#include <iostream>
 
using namespace std;
 
 
 
int N, R, C;
 
int cnt;
 
 
 
void Z(int size, int y, int x)
 
{
 
        //제일 작은 크기, 2 == (1 << 1)
 
        if (size == 2)
 
        {
 
                 if (y == R && x == C)
 
                 {
 
                         cout << cnt << "\n";
 
                         return;
 
                 }
 
                 cnt++;
 
                 if (y == R && x + 1 == C)
 
                 {
 
                         cout << cnt << "\n";
 
                         return;
 
                 }
 
                 cnt++;
 
                 if (y + 1 == R && x == C)
 
                 {
 
                         cout << cnt << "\n";
 
                         return;
 
                 }
 
                 cnt++;
 
                 if (y + 1 == R && x + 1 == C)
 
                 {
 
                         cout << cnt << "\n";
 
                         return;
 
                 }
 
                 cnt++;
 
                 return; //해당 2 * 2 블럭에 R, C가 없을 경우
 
        }
 
        //1사분면
 
        Z(size / 2, y, x);
 
        //2사분면
 
        Z(size / 2, y, x + size / 2);
 
        //3사분면
 
        Z(size / 2, y + size / 2, x);
 
        //4사분면
 
        Z(size / 2, y + size / 2, x + size / 2);
 
}
 
 
 
int main(void)
 
{
 
        cin >> N >> R >> C;
 
 
 
        Z(1 << N, 0, 0);
 
        return 0;
 
}
 
 
 
출처: https://jaimemin.tistory.com/718 [꾸준함]

감사합니다.