백준 1074 - Z

C++

1074 번 - Z

문제

2차원 배열을 Z모양으로 탐색하려고 한다.
만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
문제 출처

접근 방법

겉보기에 재귀를 써야할 것 같지만, 조건문 만을 이용하여 풀 수 있었다.
2^N의 크기인 보드를 지속하여 4등분을 하며 주어진 위치의 좌표가 4등분 된 보드 중 어느 위치에 있는지 확인한다.

또한 4등 분을 할 때마다, 각 [1, 2, 3, 4] 보드의 시작점이 달라지며, 이 시작 점의 수를 게속하여 합하는 방법으로 몇번째에 방문하는 지 알 수 있다.
따라서 만약 n = 1이면 각 등분된 시작점은 [0, 1, 2, 3]이며,
n = 2이면 [0, 4, 8, 12]
n = 3이면 [0, 16, 32, 48]
… 즉 4^N에 따라 시작점이 달라진다.

만약 주어진 예시와 같이 N이 3이고 r과 c가 7,7이면,

4등분을 3번하며, 처음 4등분 하였을시 가장 왼쪽 아래에 위치한다.
따라서 48을 더해주며, 그 다음 등분 시에도 4번의 위치, 가장 왼쪽 아래이므로 12를 더해주고, 마지막에도 동일하므로 3을 더해준다.
즉 48 + 12 + 3에 따라 정답인 63이 나온다.

구현

N의 크기만큼 반복을 해주며, 각 보드를 1/4를 하여 위치를 찾는다.
위치를 찾으면 그 좌표를 왼쪽 위로 정렬한다고 생각하고 이동시켜 준다.
즉 n = 3일때 (5,3) 점을 찾고 싶으면, 3번 위치 이므로 보드가 n=2의 크기가 되었을 시 y축 값이 (5-4, 3)이 되어 (1,3)으로 재정렬 되고 n=2의 기준으로 새로히 보드를 4등분하여 좌표가 현재 나누어진 보드의 어느 위치에 있는지 확인한다.

코드

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int n, r, c;
int result;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> r >> c;

	for (int idx = n - 1; idx >= 0; idx--) {
		int curBound = pow(2, idx);		// 4등분을 나눌 기준 선. 기준선은 2<sup>N</sup>에 따라 증가한다.
		int pst;
		if (r < curBound && c < curBound) 		// 1번 위치
			pst = 0;
		else if (r < curBound && c >= curBound) {	// 2번 위치
			pst = 1;
			c -= curBound;
		}
		else if (r >= curBound && c < curBound) {	// 3번 위치
			pst = 2;
			r -= curBound;
		}
		else {										// 4번 위치
			pst = 3;
			r -= curBound;
			c -= curBound;
		}

		result += pow(4, idx) * pst;				// 4등분 된 보드에서 현재 좌표가 위치한 자리의 시작 값을 더해준다.
	}

	cout << result;
	return 0;
}

후기 및 개선할 점

재귀적으로 생각해보려다 쉽게 떠오르지 않아, 일단 조건문으로 풀어 해결하였다.