[백준] 14601 샤워실 바닥 깔기(large)

⚡ 백준 14601 샤워실 바닥 깔기(large)

• https://www.acmicpc.net/problem/14601

• 트로미노 타일링 알고리즘

#include <iostream>
#include <utility>
#include <math.h>
using namespace std;

int board[257][257]; //2^7 * 2^7 
int tileNo = 0; //타일 번호

void fillCornersExcept(int midRow, int midCol, int flag) {

	//구멍이 있는 사분면(flag)을 제외한 나머지 가운데 모서리들 색칠 = 트로미노 한 조각

	tileNo++;
	if(flag != 1)
		board[midRow - 1][midCol - 1] = tileNo;
	if (flag != 2)
		board[midRow - 1][midCol] = tileNo;
	if (flag != 3)
		board[midRow][midCol - 1] = tileNo;
	if (flag != 4)
		board[midRow][midCol] = tileNo;

	return;
}


//트로미노 타일링 알고리즘
void tronimo(int startRow, int startCol, int size, pair<int, int> hole) {

	//base case
	if (size == 1) return;

	int midRow = startRow + size / 2;
	int midCol = startCol + size / 2;

	//각 사분면에 구멍이 없는 경우
	//그 사분면에서의 구멍의 좌표 = 각 사분면에서의 가운데 모서리의 좌표
	pair <int, int> hole1 = make_pair(midRow - 1, midCol - 1);
	pair <int, int> hole2 = make_pair(midRow - 1, midCol);
	pair <int, int> hole3 = make_pair(midRow, midCol - 1);
	pair <int, int> hole4 = make_pair(midRow, midCol);

	//사분면에 구멍이 있는 경우
	//그 사분면에서의 구멍의 좌표 = 기존 구멍의 좌표
	if (hole.first < midRow && hole.second < midCol) {
		fillCornersExcept(midRow, midCol, 1);

		hole1.first = hole.first;
		hole1.second = hole.second;
	}
	if (hole.first < midRow && hole.second >= midCol) {
		fillCornersExcept(midRow, midCol, 2);

		hole2.first = hole.first;
		hole2.second = hole.second;
	}
	if (hole.first >= midRow && hole.second < midCol) {
		fillCornersExcept(midRow, midCol, 3);

		hole3.first = hole.first;
		hole3.second = hole.second;
	}
	if (hole.first >= midRow && hole.second >= midCol) {
		fillCornersExcept(midRow, midCol, 4);

		hole4.first = hole.first;
		hole4.second = hole.second;
	}

	//재귀 호출
	tronimo(startRow, startCol, size / 2, hole1);
	tronimo(startRow, midCol, size / 2, hole2);
	tronimo(midRow, startCol, size / 2, hole3);
	tronimo(midRow, midCol, size / 2, hole4);

	return;
}

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

	int k, x, y;
	cin >> k >> x >> y;

	int size = pow(2, k);

	board[size - y + 1][x] = -1;
	tronimo(1, 1, size, make_pair(size - y + 1, x));

	for (int i = 1; i <= size; ++i) {
		for (int j = 1; j <= size; ++j) {
			cout << board[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

📌참고자료

• 트로미노 타일링 알고리즘
  https://www.youtube.com/watch?v=BFjJxA5Ym_U