[백준 / C++] 1074번 Z - 재귀 (1)

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

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

예제 입력 1 

2 3 1

예제 출력 1 

11

예제 입력 2 

3 7 7

예제 출력 2 

63

예제 입력 3 

1 0 0

예제 출력 3 

0

예제 입력 4 

4 7 7

예제 출력 4 

63

예제 입력 5 

10 511 511

예제 출력 5 

262143

예제 입력 6 

10 512 512

예제 출력 6 

786432

 

---

 

1074번 Z 문제 풀이

 

이 문제는 언뜻보면 쉬워보이나, 한 가지 큰 함정이 있다.

시간 제한을 보면 0.5초인데, 평범한 재귀를 돌리면 시간초과가 뜬다...

 

따라서, 시간 초과가 안뜨게 예외처리를 해줘야한다.

 

먼저 문제를 살펴보면 2 * 2의 배열에서만 Z를 그리면서 빠져나오는 것을 볼 수 있다. 따라서 정사각형의 크기가 2 * 2일 때 Z를 그리면서 다음 네모로 넘어간다고 보면 된다. 

 

우리가 구하는 것은 행 r과 열 c일 때 몇번째인지 구하는 것이다. 

따라서 이 네모가 내가 구하는 목적지를 포함하지 않는다면 넘어간다. 라는 예외처리를 해줘야 한다!

 

코드를 보면 아래와 같이 진행할 수 있다. 

 

---

Z 전체 코드

#include <iostream>
#include <cmath>

using namespace std;
int num = 0;
int  r, c;
int finish_flag = 0;

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

void zag( int row, int cloum) {

	
	for (int i = 0; i < 4; i++) {
		int ex_row = row + dy[i];
		int ex_cloum = cloum + dx[i];
		order++;
		if (r == ex_row && c == ex_cloum) {

			cout << order;
			finish_flag = 1;
			return;
		}
	}

	return;
}

void again(int size, int row, int cloum) {
	if (finish_flag == 1) return;

	if (size == 2) {

		zag(row, cloum);
		return;
	}
	else {
		if (row + size / 2 - 1 < r || cloum + size / 2 - 1 < c) {
			order += pow(size / 2, 2);
		}
		else {

			again(size / 2, row, cloum);
			return;
		}
		
		if (row + size / 2 - 1 < r || cloum + 2 * (size / 2) - 1 < c) {
			order += pow(size / 2, 2);
		}
		else {
			again(size / 2, row, cloum + size / 2);
			return;
		}

		if (row + 2 * (size / 2) - 1 < r || cloum + size / 2 - 1 < c) {
			order += pow(size / 2, 2);
		}
		else {

			again(size / 2, row + size / 2, cloum);
			return;
		}
		if (row + 2 * (size / 2) - 1 < r || cloum + 2 * (size / 2) - 1 < c) {
			order += pow(size / 2, 2);
		}
		else {
			again(size / 2, row + size / 2, cloum + size / 2);
			return;
		}
		return;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	int n;

	cin >> n >> r >> c;

	int size_check = 1;
	int real_size = 1;
	while (size_check <= n) {
		real_size *= 2;
		size_check++;
	}

	again(real_size, 0, 0);

	return 0;

}