[C++] 백준 1074: Z

문제

[C++] 백준 1074: Z GOLD 5

https://www.acmicpc.net/problem/1074

 

---

 

접근 방법

2^N × 2^N 크기의 배열을 Z 모양으로 방문할 때, 좌표 (r, c)가 몇 번째로 방문되는지 출력하는 문제다.

Z 방문의 핵심 규칙은 다음과 같다.

1. 큰 정사각형을 4등분(사분면) 한다.
2. 방문 순서는 항상 고정:
   왼쪽 위(0) → 오른쪽 위(1) → 왼쪽 아래(2) → 오른쪽 아래(3)
3. 목표 좌표 (r, c)가 속한 사분면만 재귀로 내려가고,
   목표 좌표가 없는 사분면은 그 사분면의 칸 수만큼을 한 번에 건너뛴다.

즉, “전부를 방문하면서 세는” 게 아니라
“필요 없는 구역은 통째로 스킵하면서 누적값(sum)만 올리는 방식” 으로 풀어야 시간 초과가 안 난다.

 

처음에 벡터를 다 채웠는데 메모리 초과가 떴고,

목표 좌표까지 모든 값을 구했더니 시간 초과가 떴다..

 

 

상세 아이디어

1) dx, dy로 사분면 순서를 고정

int dx[4] = { 0,1,0,1 };
int dy[4] = { 0,0,1,1 };

이 배열은 “현재 정사각형을 4등분했을 때, 각 사분면의 시작 좌표”를 만들기 위해 쓴다.

• i=0: (dy=0, dx=0) → 왼쪽 위
• i=1: (0,1) → 오른쪽 위
• i=2: (1,0) → 왼쪽 아래
• i=3: (1,1) → 오른쪽 아래

이 순서 자체가 Z 순서라서, for (i=0..3)로 돌면 방문 순서를 자연스럽게 유지할 수 있다.

 

2) 한 단계 내려갈 때, half로 사분면의 크기를 구함

현재 크기가 2^n × 2^n이면, 4등분한 한 사분면은

• 한 변 길이: 2^(n-1)
• 코드에서는 half = 2^n / 2

그리고 각 사분면의 시작점은 아래와 같이 계산된다.

int xx = x + (half * dx[i]);
int yy = y + (half * dy[i]);

3) 목표 좌표가 이 사분면 안에 있으면 재귀, 아니면 스킵

사분면 범위는

• y: yy ~ yy + half - 1
• x: xx ~ xx + half - 1

그래서 (r, c)가 포함되는지 체크하고 포함되면 내려간다.

if (yy <= r && r <= yy + (half - 1)) {
    if (xx <= c && c <= xx + (half - 1))
        Z(n - 1, xx, yy, sum);
    else
        sum += pow(4, (n - 1));
}
else
    sum += pow(4, (n - 1));

여기서 중요한 건 스킵할 때 더하는 값이다.

 

4) 예시를 그림으로 표현해보자면..

입력값이 "3 5 1" 이라고 한다면 다음과 같다.

 

 

구현 시 주의할 점

• 스킵 누적(sum)이 핵심이라서, 목표 좌표가 없는 사분면은 반드시 sum += 4^(n-1)로 넘겨야 한다.
  이걸 안 하면 결국 전부 탐색해서 시간 초과가 난다.
• 좌표 범위 체크에서 half - 1을 빼먹으면 범위가 한 칸씩 어긋날 수 있다.

 

---

 

코드

#include <iostream>
#include <cmath>
using namespace std;

int dx[4] = { 0,1,0,1 };
int dy[4] = { 0,0,1,1 };
int r, c;

void Z(int n, int x, int y, int sum)  // n, 출발지 x좌표, 출발지 y좌표
{
	if (n == 1)
	{
		for (int i = 0; i < 4; i++)
		{
			int yy = y + dy[i];
			int xx = x + dx[i];

			if (yy == r && xx == c)
			{
				cout << sum;
				return;
			}
			sum++;
		}
	}

	int half = pow(2, n) / 2;
	for (int i = 0; i < 4; i++)
	{
		int xx = x + (half * dx[i]);
		int yy = y + (half * dy[i]);

		if (yy <= r && r <= yy + (half - 1))  // 해당 범위 안에 (r,c)가 있다면 재귀
		{
			if (xx <= c && c <= xx + (half - 1))
				Z(n - 1, xx, yy, sum);
			else
				sum += pow(4, (n - 1));
		}
		else
			sum += pow(4, (n - 1));
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	cin >> n >> r >> c;

	Z(n, 0, 0, 0);

	return 0;
}