백준 1074번 : Z

문제 분석

• 배열을 4등분한 후 각 사각형의 각 칸을 1 → 2 → 3 → 4 순으로 방문한다.
• 각 사각형 안에서의 방문 순서는 N=2일 때의 방문 순서와 같기 때문에 위의 빨간 칸(r=6, c=2)은 1번 사각형의 모든 칸 방문 + 2번 사각형의 모든 칸 방문 + 3번 사각형에서 12번째로 방문 = 32 + 12 = 44번째로 방문한다.

✅ 결론

N=k일 때의 결과로 N=k+1의 결과를 구할 수 있다.

구현 절차

1. 함수 정의 : $2^N$ * $2^N$ 배열에서 (r,c) 를 방문하는 순서를 반환하는 함수

int func(int n, int r, int c)

2. base condition 설정 : n=0일 때 종료한다.

if(n == 0) return 0

3. 재귀 식

return func(n-1, r, c) // (r,c)가 1번 사각형에 속해 있을 때 
return half*half + func(n-1, r, c-half) // (r,c)가 2번 사각형에 속해 있을 때 
return 2*half*half + func(n-1, r-half, c) // (r,c)가 3번 사각형에 속해 있을 때
return 3*half*half + func(n-1, r-half, c-half) // (r,c)가 4번 사각형에 속해 있을 때

코드

#include <bits/stdc++.h>
using namespace std;

// (r,c)의 방문 순서를 반환
int z(int n, int r, int c) {
	// 종료 조건 
	if (n == 0) return 0;

	// 배열의 각 한 변에서 중간 지점
	int half = 1 << (n - 1); // = 2^(N-1)

	// (r,c)가
	if (r < half && c < half) return z(n - 1, r, c); // 1번 사각형에 속할 경우
	if (r < half && c >= half) return half * half + z(n - 1, r, c - half); // 2번 사각형에 속할 경우
	if (r >= half && c < half) return half * half * 2 + z(n - 1, r - half, c); // 3번 사각형에 속할 경우
	if (r >= half && c >= half) return half * half * 3 + z(n - 1, r - half, c - half); // 4번 사각형에 속할 경우
}


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, r, c;
	cin >> n >> r >> c;
	cout << z(n, r, c);

}

✅ 중간 지점 : half

크기가 $2^N$ * $2^N$ 정사각형 배열에서의 각 변의 길이는 항상 $2^N$이다.
해당 배열 탐색 시 중간 지점인 $2^N/2$ = $2^{N-1}$ 을 기준으로 전체 배열을 4개의 사분면으로 나누어 각 사분면에서 Z모양 순서로 재귀적으로 방문한다.

배열을 상하/좌우로 절반으로 나누는 기준이자 (r,c) 가 어느 사분면에 있는지 판별할 수 있게 해준다.

✅ 좌표

전체 배열을 사분면으로 나눈 후 각 사분면별 배열의 크기는 $2^{N-1}$ * $2^{N-1}$ 이다.