[1891] 사분면

---

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

1891번: 사분면

재귀를 사용하였다.

 

 

사분면을 좌표로, 좌표를 사분면으로 만드는 함수를 작성하였다.

일단 string으로 사분면 조각의 번호를 받고 int형 배열에 나눠 담아주었다.

	for (int i = 0; i < d; i++) {
		A[i] = input[i] - '0'; // char to int
	}

 

 

그 다음 생기는 좌표의 범위를 계산해주었다.

d=1일 때는 2*2 배열이 생성되고, d=3일 때는 8*8 배열이 생성되므로 

(2^d)*(2^d) 배열이 생성됨을 알 수 있다.

이 때 2의 50승(1,125,899,906,842,624)은 int형의 범위(2,147,483,647)를 넘어가므로 자료형은 long long int(9,223,372,036,854,775,807)를 써주었다.

 

 

그 다음 사분면으로 입력 받았으니 좌표로 바꿔야 한다.

그림으로 설명해보았다. 

 

아까 사분면의 조각 번호를 int형 배열에 옮겨담았었다.

제일 큰 사분면부터 시작하여 위의 조건을 d번 실행하면 좌표로 변환되어 출력할 수 있다.

void quadtoxy(ll min_x, ll max_x, ll min_y, ll max_y, int i) {
	// 사분면을 좌표로
	if (i == d) { // 사분면 자릿수 다 돌았으면
		x = min_x; y = min_y; // x, y에 넣음
		return;
	}
	ll xmid = (min_x + max_x) / 2;
	ll ymid = (min_y + max_y) / 2;

	if (A[i] == 1) { // 1사분면
		quadtoxy(xmid, max_x, min_y, ymid, i + 1);
	}
	else if (A[i] == 2) { // 2사분면
		quadtoxy(min_x, xmid, min_y, ymid, i + 1);
	}
	else if (A[i] == 3) { // 3사분면
		quadtoxy(min_x, xmid, ymid, max_y, i + 1);
	}
	else { // 4사분면
		quadtoxy(xmid, max_x, ymid, max_y, i + 1);
	}
}

 

 

이제 움직일 좌표를 입력받는다.

내 좌표는 y축이 아래로 갈 수록 증가하는 좌표이므로 입력 받은 y축 성분 값을 마이너스를 붙여준다.

	cin >> a >> b;
	b = (-b); // b는 위로 가는게(마이너스) 양수 취급을 받으므로 반대로 음수로 만들어야함
	x += a; y += b;

 

 

범위 밖이면 -1을 출력해야하므로 그에 따른 조건문을 작성한다.

	if (x >= n || x < 0 || y >= n || y < 0) { // 범위 밖이면
		printf("-1");
	}
	else {
		xytoquad(0, n, 0, n, 0);
	}

 

 

이제 다시 좌표를 사분면으로 바꿔줘야한다.

조건은 아까 그 그림과 동일하다.

void xytoquad(ll min_x, ll max_x, ll min_y, ll max_y, int i) {
	// 좌표를 사분면으로
	if (i == d) { // 사분면 다 찼으면
		return;
	}
	ll xmid = (min_x + max_x) / 2;
	ll ymid = (min_y + max_y) / 2;

	if (xmid <= x && x < max_x &&
		min_y <= y && y < ymid) { // 1사분면
		printf("1");
		xytoquad(xmid, max_x, min_y, ymid, i + 1);
	}
	else if (min_x <= x && x < xmid &&
		min_y <= y && y < ymid) { // 2사분면
		printf("2");
		xytoquad(min_x, xmid, min_y, ymid, i + 1);
	}
	else if (min_x <= x && x < xmid &&
		ymid <= y && y < max_y) { // 3사분면
		printf("3");
		xytoquad(min_x, xmid, ymid, max_y, i + 1);
	}
	else { // 4사분면
		printf("4");
		xytoquad(xmid, max_x, ymid, max_y, i + 1);
	}
}

 

 

따라서 전체 코드는 아래와 같다.

#include <iostream>
#include <cmath>
#include <string>
typedef long long int ll; // 2의 50승이 크므로
using namespace std;

int d;  int A[50];
ll x; ll y;
ll a; ll b;
string input;

void quadtoxy(ll min_x, ll max_x, ll min_y, ll max_y, int i) {
	// 사분면을 좌표로
	if (i == d) { // 사분면 자릿수 다 돌았으면
		x = min_x; y = min_y; // x, y에 넣음
		return;
	}
	ll xmid = (min_x + max_x) / 2;
	ll ymid = (min_y + max_y) / 2;

	if (A[i] == 1) { // 1사분면
		quadtoxy(xmid, max_x, min_y, ymid, i + 1);
	}
	else if (A[i] == 2) { // 2사분면
		quadtoxy(min_x, xmid, min_y, ymid, i + 1);
	}
	else if (A[i] == 3) { // 3사분면
		quadtoxy(min_x, xmid, ymid, max_y, i + 1);
	}
	else { // 4사분면
		quadtoxy(xmid, max_x, ymid, max_y, i + 1);
	}
}

void xytoquad(ll min_x, ll max_x, ll min_y, ll max_y, int i) {
	// 좌표를 사분면으로
	if (i == d) { // 사분면 다 찼으면
		return;
	}
	ll xmid = (min_x + max_x) / 2;
	ll ymid = (min_y + max_y) / 2;

	if (xmid <= x && x < max_x &&
		min_y <= y && y < ymid) { // 1사분면
		printf("1");
		xytoquad(xmid, max_x, min_y, ymid, i + 1);
	}
	else if (min_x <= x && x < xmid &&
		min_y <= y && y < ymid) { // 2사분면
		printf("2");
		xytoquad(min_x, xmid, min_y, ymid, i + 1);
	}
	else if (min_x <= x && x < xmid &&
		ymid <= y && y < max_y) { // 3사분면
		printf("3");
		xytoquad(min_x, xmid, ymid, max_y, i + 1);
	}
	else { // 4사분면
		printf("4");
		xytoquad(xmid, max_x, ymid, max_y, i + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> d >> input;
	for (int i = 0; i < d; i++) {
		A[i] = input[i] - '0'; // char to int
	}

	ll n = 1;
	for (int i = 0; i < d; i++) {
		n *= 2; // 생기는 좌표 범위는 0~n-1
	}
	quadtoxy(0, n, 0, n, 0); // 사분면을 좌표로

	cin >> a >> b;
	b = (-b); // b는 위로 가는게(마이너스) 양수 취급을 받으므로 반대로 음수로 만들어야함
	x += a; y += b; 

	if (x >= n || x < 0 || y >= n || y < 0) { // 범위 밖이면
		printf("-1");
	}
	else {
		xytoquad(0, n, 0, n, 0);
	}
}

이러케 지저분하게 푸는게 맞을까?