[BOJ] #14500 _ 테트로미노

[테트로미노] https://www.acmicpc.net/problem/14500

14500번: 테트로미노

dfs를 이용하여 모든 경우의 수를 고려하여 최대 값을 구하였다.

모든 좌표를 시작점으로 두고, 5가지의 각 테트로미노를 놓아 값을 구한 후 최대 값을 갱신해주었다.

단, 'ㅗ' 는 dfs를 이용하여 값을 구할 수 없기에 따로 하드코딩으로 값을 얻었다.

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>
#define MAX 500

using namespace std;

int dx[] = { 0, 0, -1, 1 }, dy[] = { -1, 1, 0, 0 };
int N, M, max_val = 0;
int map[MAX][MAX], chk[MAX][MAX];

void solve(int cnt, int res, int y, int x);
void getUval(int y, int x);
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			chk[i][j] = 1;
			getUval(i, j);
			solve(1, map[i][j], i, j);
			chk[i][j] = 0;
		}
	}

	printf("%d\n", max_val);

	return 0;
}

void solve(int cnt, int res, int y, int x) {
	int tmp_x, tmp_y;

	if (cnt + 1 > 4) {
		max_val = max(max_val, res);
		return;
	}

	for (int i = 0; i < 4; i++) {
		tmp_x = x + dx[i];
		tmp_y = y + dy[i];

		if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) continue;
		if (chk[tmp_y][tmp_x]) continue;

		chk[tmp_y][tmp_x] = 1;
		solve(cnt + 1, res + map[tmp_y][tmp_x], tmp_y, tmp_x);
		chk[tmp_y][tmp_x] = 0;
	}
}

void getUval(int y, int x) {
	int result;

	if (x < M - 1 && y < N - 2) {
		result = map[y][x] + map[y + 1][x] + map[y + 1][x + 1] + map[y + 2][x]; // ㅏ
		max_val = max(max_val, result);
	}

	if (x < M - 2 && y < N - 1) {
		result = map[y][x] + map[y][x + 1] + map[y + 1][x + 1] + map[y][x + 2]; // ㅜ
		max_val = max(max_val, result);
	}

	if (x > 0 && y < N - 2) {
		result = map[y][x] + map[y + 1][x] + map[y + 1][x - 1] + map[y + 2][x]; // ㅓ
		max_val = max(max_val, result);
	}
	if (x < M - 2 && y > 0) {
		result = map[y][x] + map[y][x + 1] + map[y - 1][x + 1] + map[y][x + 2]; // ㅗ
		max_val = max(max_val, result);
	}
}