백준 14500 - 테트로미노

C++

14500 번 - 테트로미노

문제

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

문제 출처

접근 방법

아쉽지만 이 블로그를 참고하여 접근 방법을 터득하였다. ㅜ를 제외한 나머지 테트로미노는 결국 DFS의 그래프 탐색으로 표현 할 수 있다. 즉, 한 점을 기준으로 모든 테트로미노를 회전, 대칭하여 탐색을 하는 것은 DFS가 한 점을 기준으로 4칸을 탐색한 것과 같다. 따라서 DFS를 통해 4칸을 상하좌우를 연달아 탐색하고, 이후 ㅜ테트로미노만 따로 탐색하는 것을 구현한다.

모든 점을 하나씩 DFS와 ㅜ 함수에 인수로 주어 탐색을 진행한다.

구현

DFS()

DFS의 그래프 탐색을 통해 4칸을 탐색을 하며 탐색을 할 때마다, 그 paper 칸의 값을 더 하여 최대 값이 될 때 마다 갱신한다. 인자로 (0,0) 부터 (n,m)까지 DFS에 하나씩 제공을 한다. 이미 하나를 선택하였으므로, DFS는 실질적으로 3개를 상 하 좌 우를 탐색한다.

aour()

이는 ㅜ테트로미노를 회전하며 하나씩 탐색 하는 함수이다. if 조건 문은 테트로미노가 들어갈 크기를 의미하며 예를 들어 ㅜ인 경우 사각형으로 2x3 만큼 차지하므로 제일 왼쪽 위의 점을 기준으로 y는 1, x는 2만큼의 크기를 차지하며 이것이 각각 n과 m이 초과하지 않게 방지를 하면 이 테트로미노가 paper그래프를 벗어나지 않게 탐색을 할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, result;
int** paper;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool visited[500][500];

void DFS(int, int, int, int);
void aour(int, int);		//ㅏ ㅗ ㅜ ㅓ

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	cin >> m;

	paper = new int* [n];
	for (int i = 0; i < n; i++)
		paper[i] = new int[m];
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> paper[i][j];
		}
	}

	for (int i = 0; i < n; i++) {			// (0,0) 부터 시작하여 (n,m)까지 점 까지 이동하며 테트리미노를 놔두면서 탐색
		for (int j = 0; j < m; j++) {
			visited[i][j] = true;
			DFS(1, paper[i][j] , i, j);
			visited[i][j] = false;
			aour(i, j);
		}
	}
	cout << result;
	return 0;
}
// ㅜ 를 제외한 나머지 테트로미노
void DFS(int lv, int sum, int y, int x) {

	if (lv == 4) {
		result = max(result, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int curY = y + dy[i];
		int curX = x + dx[i];
		if (-1 < curY && curY < n && -1 < curX && curX < m && !visited[curY][curX]) {
			visited[curY][curX] = true;
			DFS(lv + 1, sum + paper[curY][curX], curY, curX);
			visited[curY][curX] = false;
		}
	}
}
//테트로미노 중 ㅜ 인 경우 ( ㅏ ㅗ ㅜ ㅓ )
void aour(int y, int x) {
	int sum = 0;
	if (y + 2 < n && x + 1 < m) {	// ㅏ
		sum += paper[y][x];
		sum += paper[y + 1][x];
		sum += paper[y + 2][x];
		sum += paper[y + 1][x + 1];
		result = max(sum, result);
		sum = 0;
	}
	if (-1 < y - 1  && x + 2 < m) { // ㅗ
		sum += paper[y][x];
		sum += paper[y][x + 1];
		sum += paper[y - 1][x + 1];
		sum += paper[y][x + 2];
		result = max(sum, result);
		sum = 0;
	}
	if (y + 1 < n && x + 2 < m) {	// ㅜ
		sum += paper[y][x];
		sum += paper[y][x + 1];
		sum += paper[y][x + 2];
		sum += paper[y + 1][x + 1];
		result = max(sum, result);
		sum = 0;
	}
	if (y + 2 < n && -1 < x - 1) { // ㅓ
		sum += paper[y][x];
		sum += paper[y + 1][x];
		sum += paper[y + 1][x - 1];
		sum += paper[y + 2][x];
		result = max(sum, result);
		sum = 0;
	}
}

후기 및 개선할 점

후기: 처음에 주어진 모든 테트로미노를 종이에 하나씩 놔두어 가며 최댓값을 찾을려 하였다. 테트로미노를 회전, 대칭하려는 시도를 열심히 하였지만.. int** 인 동적으로 할당한 함수는 sizeof으로 배열 크기를 구 할수가 없고, 각각 다른 사이즈의 테트로미노를 vector<int**>에 저장할 수 없다는 것을 깨닫고 실패하였다. ㅠ