[백준 1074번] Z (C++)

1. 문제

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

1074번: Z

이미지 예시

2. 풀이

단순히 모든 칸을 한칸씩 다 탐색했더니 시간초과가 나왔다. 

N의 최대값을 살펴보니 15이다. 최대 size는 2의 15승이므로 32,768이 된다. 즉, 최대넓이는 32,768 x 32,768 = 1,073,741.824로 10억이 넘어간다. 결국 10억이 넘는 칸을 모두 탐색할 경우 대충 10초가 나온다.(1억번 탐색하면 약 1초가 나오므로)

 

따라서 구역을 확인 후 찾는 좌표가 없을 경우 불필요한 탐색을 없애주어야 한다.

3. 구현

1) 필자의풀이

분할정복하며 탐색해주는 dc함수를 작성하여 main함수에서 실행하였다.

 

dc함수

1. size와 오른쪽 아래의 좌표(x, y)를 받는다.
2. size가 1이면 한칸씩 한칸씩 탐색하는 중이므로 현재 좌표와 같은지 확인하고 같으면 seq를 출력하고 종료한다.
3. size와 좌표를 활용하여 탐색하려는 구역안에 찾는 좌표(r, c)가 있는지 확인한다.
4. 찾는 좌표(r, c)가 영역 안에 있으면 현재 영역을 4등분하고 1, 2의 행동을 반복한다.
5. 찾는 좌표(r, c)가 영역 안에 없으면 현재 영역의 크기(size제곱)만큼 seq에 더해준다. 

void dc(int size, int x, int y) {

	if (size == 1 && x == c && y == r) {
		cout << seq;
		return;
	}

	if (c > x - size && r > y - size && c <= x && r <= y) {
		size /= 2;
		x -= size;
		y -= size;
		dc(size, x, y);
		dc(size, x + size, y);
		dc(size, x, y + size);
		dc(size, x + size, y + size);
	}
	else {
		seq += (size * size);
	} 

}

주의할 점

• seq는 탐색 순서를 나타냈다.
• size를 구하는 과정에서 pow함수를 이용하지 않고 비트이동 연산자를 이용하여  구현하였다. (1을 n번 왼쪽비트로 이동시킴)
• 좌표계 통일
  목표 좌표(r, c)는 컴퓨터의 입장에서 행과 열이다. 그러나 사람의 입장에서는 (세로, 가로) 이므로 x축과 y축이 뒤바뀐 축(y, x)으로 보인다. 따라서 dc함수에서는 r을 y로 c를 x로 매칭시켜서 처리해 주어야 한다.
• size = 1인 상태에서 한번 더 재귀호출을 하면 size = 0이 된다. 일반적인 분할 정복에서는 size = 0인 경우 조건문으로 따로 처리하여 강제return해주어야 하지만 코드를 자세히 보면 size = 1에서 이미 강제종료가 되어 재귀함수가 더이상 호출되지 않는다.

완성된 코드

#include<iostream>

using namespace std;

int seq;
int n, r, c; 

void dc(int size, int x, int y) {

	if (size == 1 && x == c && y == r) {
		cout << seq;
		return;
	}

	if (c > x - size && r > y - size && c <= x && r <= y) {
		size /= 2;
		x -= size;
		y -= size;
		dc(size, x, y);
		dc(size, x + size, y);
		dc(size, x, y + size);
		dc(size, x + size, y + size);
	}
	else {
		seq += (size * size);
	} 

}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(NULL);
	cin >> n >> r >> c;
	int siz = (1 << n);
	dc(siz, siz-1, siz-1);
	return 0;
}

2) 모범 풀이

이미 풀었지만 더 좋은 풀이가 있어서 참고하였다. 바킹독님의 풀이이다. 매우 짧고 간결하다.

 

dc함수

1. base condition: size = 0
2. 사각형을 4등분하여 (r, c)가 어디에 있는지에 따라 반환하는 값이 달라진다.
   1) (r, c)가 1영역에 있을 때: 나머지 세 영역은 탐색할 필요가 없다.
   2) (r, c)가 2영역에 있을 때: 1영역은 이미 탐색을 끝냈으므로 1영역넓이에 2영역을 탐색한 결과를 더해야 한다.
   3) (r, c)가 3영역에 있을 때: 1, 2 영역은 이미 탐색을 끝냈으므로 1, 2 영역의 넓이에 3영역을 탐색한 결과를 더해야
   한다.
   4) (r, c)가 4영역에 있을 때: 1, 2, 3영역은 이미 탐색을 끝냈으므로 1, 2, 3영역의 넓이에 4영역을 탐색한 결과를 더해야 한다.
   (단, 각각의 경우에 대해 (r, c)의 좌표가 달라지므로 이를 고려해서 입력해준다.)
3. 이를 재귀적으로 반복하면 된다.

#include<iostream>

using namespace std;

int dc(int size, int r, int c) {
	if(size == 1) return 0;
	size /= 2;
	if (r < size && c < size) return dc(size, r, c);
	if (r < size && c >= size) return dc(size, r, c - size) + size*size;
	if (r >= size && c < size) return dc(size, r - size, c) + 2*size*size;
	if (r >= size && c >= size) return dc(size, r - size, c - size) + 3*size*size;
}

int main(void) {
	int N, r, c;
	cin >> N>> r >> c;
	int siz = (1 << N);
	cout << dc(siz, r, c);
	return 0;
}