14600 샤워실 바닥 깔기 (Small) C++

분할정복의 대표적인 트로미노 알고리즘 문제

ㄱ자 모양의 블럭으로 모든 칸을 뒤덮을 수 있는가?(있음)

종만북 분할정복에 있었던 문제같은데 오랜만에 보니 반가웠다

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

1. 문제

---

간단 설명

2^K 칸의 맵이 주어질 때, 이 칸을 배수구를 제외한 모든 칸을 ㄱ자 블럭으로 덮을 수 있을까?

맵이 작아서 K=1, K=2로 나누어

모든 경우의 수를 직접 노가다로 구현해도 상관없지만

분할정복 연습을 위해서 분할 정복으로 풀어봄

이 문제를 풀기위해선 먼저 트로미노 타일링이라는 사전지식이 필요함

트로미노 타일링이란?

1) 트로미노란?

크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형

ㄱ자 모양과 일자 모양 두가지가 있지만, 여기선 ㄱ자 모양만 이용함

2) 2^n * 2^n 타일을 ㄱ자로 다 덮을 수 있는가?

이를 증명하기 위해서 수학적 귀납법을 사용함

귀납법

1. N=1일때 성립함을 증명
2. N=K일때 참이라고 가정, N=K+1도 참임을 증명

1. N=1일때 성립함을 증명

참. 어떠한 경우에도 3칸을 채우고, 나머지 한칸은 배수구로 채울 수 있음

1. N=K가 참이라고 가정하고, N=K+1이 참임을 증명

N=K일때, 즉 한 변의 길이가 2^k라고 할 때,

배수구 한칸을 제외하고 모두 채울 수 있다고 가정하면

N=K+1일때, 즉 한변의 길이가 2^(K+1) 인 경우,

배수구 한칸을 제외하고 모두 채울 수 있다.

이를 통해 배수구 한칸만 있다면, 모든 칸을 ㄱ자 블럭으로 덮을 수 있음을 증명함

이를 구현해보자

2. 문제 분석

---

필요변수

맵 크기 int k (1<=k<=2)

맵 int map[5][5];

배수구 위치 int x, y

주의점

• 주어진 좌표계가 일반적으로 사용하는 y,x 좌표계가 아님에 주의
• 분할 정복시 배열 인덱스 주의
• 시작 좌표가 (0,0)이 아니라 (1,1)임

알고리즘

1. 맵 크기 k를 입력받고, 배수구의 위치 x,y를 입력받는다
2. (0, 0)부터 타일을 깔아본다
3. 크기가 2보다 크다면 4등분해서, 중앙 지점에 ㄱ자 블럭을 놓는다
4. 이후 4등분한 조각을 다시 재귀적으로 호출해서 ㄱ자 블럭을 놓는다
5. 만약 크기가 2라면 더이상 쪼개지 않고 리턴
6. 전체 타일을 출력한다 

3. 소스코드

---

#include <iostream>

using namespace std;

int k;
int x, y;
int map[5][5];
int num = 0;

// 주어진 정사각형이 모두 비어있는지 체크하는 함수
// 배수구(-1)가 있으면, false 리턴함
bool check(int sz, int x, int y) {
	for (int i = x; i < x + sz; i++) {
		for (int j = y; j < y + sz; j++) {
			if (map[i][j] != 0) 
				return false;
		}
	}
	return true;
}

// 분할정복
// x, y, sz를 받아 4부분으로 쪼개서 가능한지 확인한다
void sol(int x, int y, int sz) {
	num++;
	int s = sz / 2;

	// 왼쪽 아래 (1,1)~(2,2) 블럭을 놓을 수 있다면 놓고, 아니라면 패스
	if (check(s, x, y)) { map[x + s - 1][y + s - 1] = num; }
	// 오른쪽 아래 (1,3)~(2,4)
	if (check(s, x, y + s)) { map[x + s - 1][y + s] = num; }
	// 왼쪽 위 (3,1)~(4,2)
	if (check(s, x + s, y)) { map[x + s][y + s - 1] = num; }
	// 오른쪽 위 (3,3)~(4,4)
	if (check(s, x + s, y + s)) { map[x + s][y + s] = num; }

	if (sz == 2) return; // 최소 단계. 더이상 나누어지지 않으면 재귀호출을 하지 않고 종료

    // 4등분한 부분을 재귀호출한다
	sol(x, y, s);
	sol(x + s, y, s);
	sol(x, y + s, s);
	sol(x + s, y + s, s);

}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> k;
	cin >> x >> y;

	map[y-1][x-1] = -1;

	sol(0, 0, 1 << k); // (1,1)에서 시작, 2^K칸

	for (int i = (1 << k) - 1; i >= 0; i--) {
		for (int j = 0; j < (1 << k); j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}

분할정복을 사용한 풀이이므로, large 문제에도 적용 가능함. 대신 맵 사이즈만 수정하면 될듯

분할 정복을 더 공부해봐야겠다