[BOJ] 14500 테트로미노

Link https://www.acmicpc.net/problem/14500

Note

1x1 정사각형 4개로 이루어진 테트로미노를 n x m 크기의 종이에 최대한 배치 할 때, 테트로미노가 놓인 칸의 수의 합을 출력해준다.

일단 이 문제를 보았을 때 떠올린 방법은 나올 수 있는 모든 경우의 수를 배열에 넣어 배치하는 방법밖에 안떠올랐다.
이 후, 다른 해답들을 보면서 DFS로 이 문제가 해결 가능하다는 것을 알았다.
문제에서 주어진 도형을 회전과 대칭을 이용해서 나올 수 있는 경우의 가지수는 총 19가지.
19가지의 방법의 가로, 세로크기가 각각 다 다르기 때문에 각각의 경우를 19칸 배열에 저장하고, 각각의 경우를 0과 1로 이루어진 int 2차원 배열에 넣었다.
알고리즘이라 할 만한게 없다 19개 블럭만 잘 지정해 준뒤 가능한 모든 칸에 다 비교해 볼 뿐.

알고리즘

1. 19가지 경우의 수의 가로, 세로, 테트로미노를 초기화한다.
2. 0,0 부터 n,m 까지 19가지의 테트로미노를 다 대입해 최대 값을 갱신한다.
3. 출력한다.

소스코드

#include <iostream>

using namespace std;

const short MAX = 500;
const short TETRO_MAX = 19;

short board[MAX][MAX];

const short sizeX[TETRO_MAX] = { 4, 1, 2, 2, 2, 3, 2, 3, 2, 2, 3, 3, 2, 3, 2, 3, 2, 3, 3 };
const short sizeY[TETRO_MAX] = { 1, 4, 2, 3, 3, 2, 3, 2, 3, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2 };

bool tetro[TETRO_MAX][4][4];

void initTetro()
{
	tetro[0][0][0] = tetro[0][1][0] = tetro[0][2][0] = tetro[0][3][0] = 1;
	tetro[1][0][0] = tetro[1][0][1] = tetro[1][0][2] = tetro[1][0][3] = 1;
	tetro[2][0][0] = tetro[2][0][1] = tetro[2][1][0] = tetro[2][1][1] = 1;
	tetro[3][0][0] = tetro[3][0][1] = tetro[3][0][2] = tetro[3][1][2] = 1;
	tetro[4][1][0] = tetro[4][1][1] = tetro[4][1][2] = tetro[4][0][2] = 1;
	tetro[5][0][0] = tetro[5][0][1] = tetro[5][1][0] = tetro[5][2][0] = 1;
	tetro[6][0][0] = tetro[6][1][0] = tetro[6][1][1] = tetro[6][1][2] = 1;
	tetro[7][0][1] = tetro[7][1][1] = tetro[7][2][1] = tetro[7][2][0] = 1;
	tetro[8][0][0] = tetro[8][0][1] = tetro[8][1][1] = tetro[8][1][2] = 1;
	tetro[9][1][0] = tetro[9][1][1] = tetro[9][0][1] = tetro[9][0][2] = 1;
	tetro[10][0][1] = tetro[10][1][1] = tetro[10][1][0] = tetro[10][2][0] = 1;
	tetro[11][0][0] = tetro[11][1][0] = tetro[11][2][0] = tetro[11][1][1] = 1;
	tetro[12][1][0] = tetro[12][1][1] = tetro[12][1][2] = tetro[12][0][1] = 1;
	tetro[13][1][0] = tetro[13][0][1] = tetro[13][1][1] = tetro[13][2][1] = 1;
	tetro[14][0][0] = tetro[14][0][1] = tetro[14][0][2] = tetro[14][1][1] = 1;
	tetro[15][0][0] = tetro[15][0][1] = tetro[15][1][1] = tetro[15][2][1] = 1;
	tetro[16][0][0] = tetro[16][1][0] = tetro[16][0][1] = tetro[16][0][2] = 1;
	tetro[17][0][0] = tetro[17][1][0] = tetro[17][2][0] = tetro[17][2][1] = 1;
	tetro[18][0][0] = tetro[18][1][0] = tetro[18][1][1] = tetro[18][2][1] = 1;
}

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

	initTetro();

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];

	int res = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < TETRO_MAX; k++) {
				short ranX = j + sizeX[k];
				short ranY = i + sizeY[k];

				if (0 <= ranX && ranX <= m && 0 <= ranY && ranY <= n) {
					int sum = 0;

					for (int row = 0; row < sizeX[k]; row++)
						for (int col = 0; col < sizeY[k]; col++) {
							sum += board[i + col][j + row] * tetro[k][row][col];
						}

					if (res < sum)
						res = sum;
				}
			}
		}
	}

	cout << res;

	return 0;
}

2019-06-02 19:03:00에 Tistory에서 작성되었습니다.