[Beakjoon Online Judge] 1074 - Z(C++)

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

N=3일 때 예시

 

문제는 위와 같다.

재귀적인 움직임을 보이기 때문에 규칙을 만들어 해당 위치까지 하나씩 찾아가면 풀 수 있겠으나,

코딩테스트 특성상 "시간 초과"라는 무서운 친구가 있기 때문에 조금 고차원적으로 접근을 해봐야했다.

 

주의점 : N이 15이하의 자연수로 주어지는데, 2의 15승은 int의 표현 범위를 벗어나기 때문에 long long으로 사용해야한다.

 

일단 2의 제곱들과 관련된 문제니까 무의식적으로 2의 제곱을 계산해주는 함수를 만들었다. 의미는 없다.

long long twoPow(int count)
{
	int i;
	long long num;
	num = 1;
	for(i=0;i<count;i++)
		num*=2;
	return num;
}

 

그리고 한참 생각해본 후 깨달은 것은, "경로를 그릴 필요가 없다"는 점이다.

재귀의 형태가 정사각형이고, 가장 큰 판에서 4등분해나가면 2x2의 Z가 나온다.

 

그래서 수학에서 자주 봤던 사분면을 떠올리며 함수를 만들었다.

int whereQuadrant(long long r, long long c, long long size, long long x, long long y)
{
	/*
	1 2
	3 4
	*/
    
	//cout << size << "에서 " << r << " " << c <<"랑 " << size+x << " " << size+y << " 비교" << endl;
	
	size /= 2;

	if(r<size+x&&c<size+y)
		return 1;
	else if(r<size+x&&c>=size+y)
		return 2;
	else if(r>=size+x&&c<size+y)
		return 3;
	else if(r>=size+x&&c>=size+y)
		return 4;
}

대신 이 함수는 Z의 순서에 따라 왼쪽위가 제1사분면이고 오른쪽아래가 제4사분면으로 반환하게 만들었다.

(중간에 주석은 이 함수가 어떻게 굴러가는지 보려고 문제 풀 때 만들어놓고 귀찮아서 안지웠다.)

 

r,c가 어떤 size의 평면에서 몇사분면인지 반환하는데, x와 y의 역할은 (0,0)에서 사분면을 이동하는 데 쓴다.

무슨 말인지 모르겠다면 일단 다음 사진을 보자

 

이 평면은 2^5 x 2^5의 크기(N=5)고, A라는 점의 좌표는 (2,26)이다.

알고리즘을 짜보겠다.

 

1. 32 x 32의 평면을 16 x 16 평면 네 개로 쪼갠다. -> (2,26)은 2사분면에 속한다.
2. 1의 2사분면인 16 x 16 평면을 8 x 8 평면 네 개로 쪼갠다. -> (2,26)은 2사분면에 속한다.
3. 2의 2사분면인 8 x 8 평면을 4 x 4 평면 네 개로 쪼갠다. -> (2,26)은 1사분면에 속한다.
4. 3의 1사분면인 4 x 4 평면을 2 x 2 평면 네 개로 쪼갠다. -> (2,26)은 4사분면에 속한다.
5. 4의 4사분면인 2 x 2 평면을 1 x 1 평면 네 개로 쪼갠다. -> (2,26)은 1사분면에 속한다.

 

whereQuadrant() 함수를 통해 점이 어느 사분면에 속하는지는 알아냈다.

이쯤되면 이걸 왜 구했는지 궁금할 수 있는데, 아무리 헷갈리게 Z자를 그리며 이동하더라도 결국 모든 좌표를 한번씩 거친다는 것을 생각해보면 쉽게 답이 나온다.

 

바로 위에 1번에서 (2,26)이 2사분면에 속한다는 것은, 이미 1사분면에 있는 모든 점은 다 거쳤다는 것이다.

또한 4번에서 (2,26)이 4사분면에 속한다는 것은, 이미 1사분면 2사분면 3사분면의 모든 점을 다 거쳤다는 것이다.

 

한 사분면의 크기는 2^(N-1) x 2^(N-1)이기 때문에 결국 점점 작아지는 각 사분면의 크기를 계속 더해주면 된다.

언제까지? 사분면의 크기가 1 x 1이 될 때까지!

 

x와 y라는 변수는 whereQuadrant() 라는 함수를 두번째 시행했을 때, 첫번째의 2사분면에서 사분면을 나눠 (2,26)을 비교해야하는데 첫번째의 1사분면에서 사분면을 나눠 비교해 이상한 결과를 도출하기 때문에 사분면의 기준을 바꿔주는 역할을 한다. 바꿔주지 않으면 몇번을 시행하더라도, (r,c)가 우측 맨 하단에 있더라도 계속 1사분면에서 비교하기 때문에 4사분면만 계속 반환해 잘못된 루프에 빠질 수 있다.

 

좀 코드가 더럽지만 깔끔하게 올릴 생각은 없기 때문에 나의 답안은 다음과 같다.

#include <iostream>
using namespace std;
long long twoPow(long long count)
{
	// 위 참고
}
int whereQuadrant(long long r, long long c, long long size, long long x, long long y)
{
	// 위 참고
}
int main()
{
	long long N, r, c, answer = 0;
	long long twoN;
	int NQ; // NQuadrant
	long long x, y;
	x = y = 0; 
	cin >> N >> r >> c;
	twoN = twoPow(N);
	while(1)
	{
		NQ = whereQuadrant(r,c,twoN,x,y);
		twoN /= 2;
		answer += ((NQ-1)*twoN*twoN);
		if(NQ==2)
			y+=twoN;
		else if(NQ==3)
			x+=twoN;
		else if(NQ==4)
		{
			x+=twoN;
			y+=twoN;
		}
		if(twoN==1)
			break;
	}
	cout << answer << endl;
	return 0;
}

 

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 1074번 Z C++

BOJ 1074번 Z C++

백준 1074번 Z C++