백준 - 14500 테트로미노

문제

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

14500번: 테트로미노

주어진 맵에서 각각의 테트로미노를 회전, 대칭해서 최댓값을 찾는 문제였다.

 

문제 풀이

500x500의 맵이고 회전과 대칭을 한 테트로미노의 총 개수가 19개였다. 대략 5,000,000 정도가 나왔고, 각각의 합을 더해줄 때 각 테트로미노마다 4번의 연산이 필요하기 때문에 20,000,000 정도가 나왔다. 제한 시간이 2초로 아주 넉넉했기 때문에 완전 탐색으로 풀었다.

 

처음에는 회전하는 메소드를 만들어서 활용하고자 했는데, 규칙을 찾기가 조금 까다롭고 회전하는 양이 그렇게 많지 않아서 하드코딩으로 값을 넣어줬다. 대칭 시키는 함수는 만들어 사용했다.

 

그리고 이렇게 만든 각각의 테트로미노들을 맵의 처음부터 끝까지 이동하며 최대 합을 찾았다. 그리고 이런 합들 중 가장 큰 값이 답이었다.

 

이번 문제에서는 테트로미노의 개수가 얼마 없어서 하드코딩이 가능했는데, 만약 수가 10개가 나온다거나.. 한다면 회전하는 방법을 찾긴 해야할 것 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

/*
500x500 x 19(회전, 대칭 포함) -> 5000000 * 4(내부인지 확인) -> 20000000
1. 회전/대칭한 모양까지 모두 저장
2. 각각의 모양으로 맵의 처음부터 끝까지 탐색

맨 끝 위가 i,j라고 할 때 (0,0부터 시작)

하늘색 -> i,j  i,j+1  i,j+2  i,j+3 -> 0,0  0,1  0,2  0,3
노란색 -> i,j  i,j+1  i+1,j  i+1,j+1
...
*/

vector<vector<pair<int,int>>> tetrominos; //dx, dy
int N, M;
int map[500][500];


vector<pair<int, int>> symmetrlyTetromino(vector<pair<int, int>> tetromino) { //아래로 대칭
	int maxHeight = 0;
	for (int i = 0; i < 4; i++) {			
		maxHeight = max(maxHeight, tetromino[i].first);
		tetromino[i].first = -tetromino[i].first;
	}

	for (int i = 0; i < 4; i++) {
		tetromino[i].first += maxHeight;
	}

	return tetromino;
}

void initTetromino() {
	//하늘색
	tetrominos.push_back({ {0,0},{0,1},{0,2},{0,3} });
	tetrominos.push_back({ {0,0},{1,0},{2,0},{3,0} });

	//노란색
	tetrominos.push_back({ {0,0},{0,1},{1,0},{1,1} });

	//주황색
	tetrominos.push_back({ {0,0},{2,0},{2,1},{1,0} });
	tetrominos.push_back({ {0,2},{0,1},{0,0},{1,0} });
	tetrominos.push_back({ {2,1},{1,1},{0,1},{0,0} });
	tetrominos.push_back({ {1,0},{1,1},{1,2},{0,2} });
	for (int i = 0; i < 4; i++) {
		tetrominos.push_back(symmetrlyTetromino(tetrominos[i + 3]));
	}

	//초록색
	tetrominos.push_back({ {0,0},{1,0},{1,1},{2,1} });
	tetrominos.push_back({ {0,1},{0,2},{1,1},{1,0} });
	tetrominos.push_back(symmetrlyTetromino(tetrominos[11]));
	tetrominos.push_back(symmetrlyTetromino(tetrominos[12]));

	//분홍색
	tetrominos.push_back({ {0,0},{0,1},{0,2},{1,1} });
	tetrominos.push_back({ {0,0},{1,0},{2,0},{1,1} });
	tetrominos.push_back({ {0,1},{1,0},{2,1},{1,1} });
	tetrominos.push_back(symmetrlyTetromino(tetrominos[15]));
	
}

int findMaxSum(vector<pair<int, int>> tetromino) {

	int sum;
	int maxSum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			sum = 0;
			for (int k = 0; k < 4; k++) { //각각의 칸
				int x = tetromino[k].first + i;
				int y = tetromino[k].second + j;

				//printf("x: %d y: %d\n", x, y);
				if (x >= 0 && x < N && y >= 0 && y < M) {
					sum += map[x][y];
				}
				else {
					sum = -1;
					break;
				}
			}
			maxSum = max(maxSum, sum);
			//printf("sum: %d\n", sum);
		}
	}
	//printf("maxSum: %d\n", maxSum);
	return maxSum;
}

int main(int argc, char** argv)
{
	scanf("%d %d", &N, &M);
	int answer = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	//테트로미노 모양 저장
	initTetromino();

	for (int i = 0; i < tetrominos.size(); i++) {
		//printf("tetromino %d\n", i);
		answer = max(answer, findMaxSum(tetrominos[i]));
	}

	printf("%d", answer);
	return 0;
}