[BOJ] 1074번_Z_분할정복 (C++)

[문제]

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

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

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

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

*분할정복 문제는 처음이라 구글링을 통해 다른 사람의 코드를 참고했다.

[사용 알고리즘]

분할정복

[풀이 핵심]

• 분할정복이란 기본적으로 엄청 큰 문제를 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하는 개념이다. 해당 문제에서는 입력받은 큰 정사각형을 분할해서 크기가 4인 정사각형으로 만들어 해결하는 것이 핵심이다.
• 현재 정사각형 범위안에 찾으려는 열과 행이 존재할 경우, 4등분으로 나눠 Z자로 탐색하고, 나눈 정사각형 중 찾으려는 열과 형이 존재하는 정사각형을 또 4등분으로 나눠 Z자로 탐색하며, 행과 열을 찾으면 된다. (재귀)
• 답은 주어진 칸에 몇 번째로 방문하는지 출력하는 것이므로 탐색하는 정사각형 내에 주어진 칸이 없으면 해당 정사각형을 전부 탐색한 것으로 생각하고 size * size(정사각형의 크기)만큼 탐색횟수를 더해주면 된다.
• 이 문제에는 주의해야할 점이 하나 있는데, 배열에 탐색횟수를 저장해가며 풀게 될 경우 메모리 초과, 시간 초과가 날 수 있다. N의 최대 입력값이 15이기 때문에, 2차원 배열을 선언하면 배열의 크기가 2^15 * 2^15 = 2^30이기 때문이다.

[코드]

//boj1074번_Z_분할정복

#include<iostream>
#include<cmath>

using namespace std;

int N, r, c;
int result = 0;

void Z(int x, int y, int size) {
	if (x == c && y == r) {
		cout << result;
		return;
	}
	if (c < x + size && r < y + size && c >= x && r >= y) {
		Z(x, y, size / 2);
		Z(x + size / 2, y, size / 2);
		Z(x, y + size / 2, size / 2);
		Z(x + size / 2, y + size / 2, size / 2);
	}
	else {
		result += size * size;
	}
}

int main() {
	cin >> N;
	cin >> r >> c;

	Z(0, 0, pow(2,N));
}