[백준알고리즘] 14601번: 샤워실 바닥 깔기 (Large)-C++

14601번: 샤워실 바닥 깔기 (Large) (acmicpc.net)

14601번: 샤워실 바닥 깔기 (Large)

분할 정복을 사용해야 하는 문제인 것은 감이 왔는데, 어떻게 분할 정복을 적용할지가 고민이었다. 그래서 생각보다 시간이 꽤 소요됐다.

처음에 생각했던 방식은 큰 'ㄱ'자 모양들로 분할해 나가는 것이다. 그런데 이건 큰 'ㄱ'자 모양 안에 작은 'ㄱ'자 타일들로 배치하는 게 생각보다 귀찮은 문제로 다가왔다.

다음으로 생각한 것은 큰 정사각형 모양을 작은 정사각형 4개로 분류하고, 각각의 작은 정사각형에서 한 칸씩만 칸을 뚫는 것을 생각했다. 결과적으로 이 방식을 사용했다.

---

문제 풀이

전체 큰 사각형을 길이가 절반인 정사각형 4개로 분리했다. 그리고, 이 4개의 정사각형이 모이는 가운데 부분에 'ㄱ'자 모양 블럭을 하나 떼어놓았다. 이때, 타일이나 배관이 설치되어 있는 정사각형은 가운데 부분에 모인 4개의 블록 가운데 'ㄱ'자 타일에 포함되지 않는 공간을 갖도록 했다.

 

따라서, 이 4개의 작은 정사각형이 모이는 부분에 있는 'ㄱ'자 타일들을 먼저 숫자들로 채워나갔다.

 

이제 이것을 반복적으로 각각의 작은 정사각형에 적용했다. 각 정사각형에서는 4개의 더 작은 정사각형 공간으로 분리를 했다. 배관이 없더라도, 가운데에 'ㄱ'자 타일을 놓느라 공간을 쓴 더 작은 정사각형은 어차피 타일을 깔지 못하기 때문에 배관이 놓인 것과 동일하게 취급한다.

 

전체 공간의 길이가 2^k 이면서 배관은 한 개만 존재하기 때문에, 타일을 배치하는 방법이 없는 경우는 없다.

 

오늘은 피곤해서 더 함수들을 정리해보지는 못했다.

그리고 신기한건 다른 사람들이 어떻게 풀었나 구경했더니 풀이 방법들이 다 같아 보였다. 다른 방식으로 푼 게 있으면 어떻게 접근했나 궁금하다.

#include <cstdio>
#include <cmath>

int room[129][129];
int count = 0;

void tile(const unsigned int uiStartX, const unsigned int uiStartY, const unsigned int uiLen);
bool isEmptySpace(const unsigned int uiStartX, const unsigned int uiStartY, const unsigned int uiLen);

int main(void) {
	unsigned int uiSide = 0;
	scanf("%u", &uiSide);
	unsigned int uiPipeX = 0;
	unsigned int uiPipeY = 0;
	scanf("%u %u", &uiPipeX, &uiPipeY);

	unsigned int uiLen = (unsigned int) ::pow(2, uiSide);
	room[uiPipeY][uiPipeX] = -1;
	tile(1, 1, uiLen);

	for ( unsigned int y = uiLen; y >= 1; --y ) {
		for ( unsigned int x = 1; x <= uiLen; ++x ) {
			printf("%d ", room[y][x]);
		}
		printf("\n");
	}

	return 0;
}

void tile(const unsigned int uiStartX, const unsigned int uiStartY, const unsigned int uiLen) {
	unsigned int uiHalf = uiLen >> 1;

	++count;

	if ( true == isEmptySpace(uiStartX, uiStartY, uiHalf) ) {
		room[uiStartX + uiHalf - 1][uiStartY + uiHalf - 1] = count;
	}
	if ( true == isEmptySpace(uiStartX + uiHalf, uiStartY, uiHalf) ) {
		room[uiStartX + uiHalf][uiStartY + uiHalf - 1] = count;
	}
	if ( true == isEmptySpace(uiStartX, uiStartY + uiHalf, uiHalf) ) {
		room[uiStartX + uiHalf - 1][uiStartY + uiHalf] = count;
	}
	if ( true == isEmptySpace(uiStartX + uiHalf, uiStartY + uiHalf, uiHalf) ) {
		room[uiStartX + uiHalf][uiStartY + uiHalf] = count;
	}

	if ( 2 == uiLen ) {
		return;
	}

	tile(uiStartX, uiStartY, uiHalf);
	tile(uiStartX + uiHalf, uiStartY, uiHalf);
	tile(uiStartX, uiStartY + uiHalf, uiHalf);
	tile(uiStartX + uiHalf, uiStartY + uiHalf, uiHalf);
}

bool isEmptySpace(const unsigned int uiStartX, const unsigned int uiStartY, const unsigned int uiLen) {
	for ( unsigned int x = 0; x < uiLen; ++x ) {
		for ( unsigned int y = 0; y < uiLen; ++y ) {
			if ( 0 != room[uiStartX + x][uiStartY + y] ) {
				return false;
			}
		}
	}
	return true;
}