백준(BOJ)14500번 테트로미노

안녕하세요? 오늘은 백준 알고리즘 사이트에 게시된 문제 중 하나인 14500번 테트로미노 문제를 풀어보겠습니다.

먼저 문제를 읽어보겠습니다. 

이 문제를 처음 봤을 때, 어릴 적 추억이 떠올랐습니다.

테트리스는 지금까지고 인기있는 게임인데요, 다음에 테트리스 게임과 봇을 만들어서 구현 방법과 알고리즘에 대해 포스팅하도록 하겠습니다.

간단하게 문제의 요지를 적는다면, 입력으로 NxM의 여러 숫자가 포진되어 있는 맵이 주어지고 각각의 테트로미노가 맵에 놓였을 때 생기는 테트로미노와 맵과의 교집합의 최대값을 구하라는 문제입니다.

제가 사용한 알고리즘은 다음과 같습니다.

이 문제가 다소 까다로운 이유는 이 테트로미노가 대칭과 회전이 가능하다는 것입니다. 전 이 문제를 모든 테트로미노의 모양을 맵에 대입해서 결과값을 구하는 완전 탐색으로 접근했습니다.

그렇다면 이 완전 탐색 기법이 과연 이 문제에 적합한가를 살펴보기 위해 대략적인 시간복잡도를 구해보았습니다.

테트로미노(T)의 모양이 총 5가지이며, 대칭과 회전을 통해 나올 수 있는 모양은 총 19가지입니다. 주어지는 맵의 width를 M, height를 N으로 보고 각각의 테트로미노의 width를 m, height를 n으로 정의하면, 다음과 같은 대략적인 연산의 개수를 셀 수식을 세울 수 있습니다.

위 식에 빅오 표기법을 적용하면 다음과 같은 시간복잡도를 얻을 수 있습니다. 

그럼 이제 구현에 대해 설명하겠습니다.

먼저 각각의 테트로미노를 좌표 이동 방법으로 표현하였습니다. 도식화해서 설명드리면 다음과 같습니다.

다음과 같은 테트로미노가 있고, 중심에 진한 부분은 이 테트로미노의 중심입니다.

이 중심을 기준으로 현재 떨어진 위치를 사용하여 좌표이동이 가능하도록 하였습니다.

즉, 현재 위치에서 x, y의 거리의 차를 이용하여 19개의 테트로미노를 표현하였습니다.

소스코드는 다음과 같습니다.

#include <iostream>
using namespace std;

int map[505][505];
int N, M;
bool isInRange(int x, int y) {
	if (x < 0 || x >= M || y < 0 || y >= N)
		return false;
	return true;
}
int main() {
	int block_num = 5;
	int shape_num[5] = { 2, 4, 8, 4, 1 };
	int blocks[5][8][2][4] = {
							{ 
								{ {0, -1, 1, 2}, {0, 0, 0, 0} },
								{ {0, 0, 0, 0}, {0, -1, 1, 2} } },

							{ 
								{ {0, 0, 1, 1}, {0, -1, 0, 1} },
								{ {0, 0, -1, -1}, {0, -1, 0, 1} },
								{ {0, -1, 0, 1}, {0, 0, -1, -1} },
								{ {0, 0, -1, 1},  {0, -1, -1, 0} } },

							{ 
								{ {0, 0, 0, 1}, {0, -1, -2, 0} },
								{ {0, -1, 0, 0}, {0, 0, -1, -2} },
								{ {0, 0, 1, 2}, {0, 1, 0, 0} },
								{ {0, -1, -2, 0}, {0, 0, 0, 1} },
								{ {0, -1, 0, 0 }, {0, 0, 1, 2} },
								{ {0, 1, 0, 0}, {0, 0, 1, 2} },
								{ {0, 0, -1, -2}, {0, -1, 0, 0} },
								{ {0, 0, 1, 2}, {0, -1, 0, 0} } },

							{ 
								{ {0, -1, 1, 0}, {0, 0, 0, 1} },
								{ {0, -1, 0, 0}, {0, 0, -1, 1} },
								{ {0, 0, 0, 1}, {0, -1, 1, 0} },
								{ {0, -1, 1, 0}, {0, 0, 0, -1}} },

							{ 
								{ {0, 0, 1, 1}, {0, 1, 0, 1} } } };

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	int dx[4], dy[4];
	int sum = 0;
	int max_sum = -1;
	int cur_X, cur_Y;
	for (int block = 0; block < block_num; block++) {
		for (int shape = 0; shape < shape_num[block]; shape++) {
			for (int pair = 0; pair < 4; pair++) {
				dx[pair] = blocks[block][shape][0][pair];
				dy[pair] = blocks[block][shape][1][pair];
			}
			for (int h = 0; h < N; h++) {
				for (int w = 0; w < M; w++) {
					bool pass = true;
					sum = 0;
					for (int d = 0; d < 4; d++) {
						cur_X = w + dx[d];
						cur_Y = h + dy[d];
						if (!isInRange(cur_X, cur_Y)) {
							pass = false;
							break;
						}
					}
					if (pass == true) {
						for (int d = 0; d < 4; d++) {
							sum += map[h + dy[d]][w + dx[d]];
						}
						if (max_sum < sum)
							max_sum = sum;
					}
				}
			}
		}
	}
	cout << max_sum << endl;
	return 0;
}

테트로미노의 순서는 다음과 같습니다. 

테트로미노의 첫 번째 도형이, 두 번째 도형이로 생각하시면 됩니다.

이상으로 글을 마치겠습니다.