[C++/백준] 1074번-Z

링크

---

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

문제

---

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

풀이

---

쉽게 재귀로 접근해서 풀어보려 하였으나 시간초과로 인해 각 재귀에 조건문을 달아주어야 했다.

4가지 경우로 나누어 오른쪽 아래에서 찾아야 하는 수라면 나머지 3개의 면에 있는 순서를 재귀를 돌리지 않고 계산하여 더해주는 방식으로 설계하였다.

코드

---

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

int N;
int r, c;
int result = -1;
bool flag = false;

void recurse(int x, int y, int size) {
	if (flag)
		return;
	else {
		if (size == 1) {
			result++;
			if (x == r && y == c) {
				flag = true;
				return;
			}
		}
		else {
			if (r < size / 2 + x && c < size / 2 + y) {
				recurse(x, y, size / 2);
			}
			else if (r < size / 2 + x && c >= size / 2 + y) {
				result += (size / 2) * (size / 2);
				recurse(x, y + size / 2, size / 2);
			}
			else if (r >= size / 2 + x && c < size / 2 + y) {
				result += (size / 2) * (size / 2) * 2;
				recurse(x + size / 2, y, size / 2);
			}
			else if (r >= size / 2 + x && c >= size / 2 + y) {
				result += (size / 2) * (size / 2) * 3;
				recurse(x + size / 2, y + size / 2, size / 2);
			}
		}
	}

	return;
}

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

	recurse(0, 0, pow(2, N));

	cout << result;

	return 0;
}