[ 백준 ] 14500번 테트로미노 _ 완전 탐색

완전 탐색인 문제이기 때문에 모든 경우의 수를 탐색했다

각 꼭지점이 겹쳐져야 되기에 기준의 되는 블록을 기준으로 상하좌우로 전체 탐색을 하면된다. 

하지만, 이 경우 ㅏ 모양의 테트로미노가 불가능하기에 대각선에 대해서도 모든 경우를 탐색해줬다.

 

그렇기에 상하좌우를 확인하는 if 문 4개와 4개의 대각선을 확인하는 if문 4개로 구성된다. 

대각선을 확인할 때는 연결되야되기에 안에 if문이 추가되었다. 

#include<stdio.h>
int space[510][510];
int n, m = 0;
int max = 0;
int search(int i, int j ,int score,int count) {
	int empty_box = space[i][j];
	score += empty_box;
	space[i][j] = -1;

	if (count == 3) {
		space[i][j] = empty_box;
		return score;
	}
	int s_max = -1;
	int box = 0;
	if (i + 1 < 501) {
		if (space[i + 1][j] != -1) {
			box = search(i + 1, j, score, count + 1);
			if (s_max < box)
				s_max = box;
		}
	}
	if (j + 1 < 501) {
		if (space[i][j + 1] != -1) {
			box = search(i, j + 1, score, count + 1);
			if (s_max < box)
				s_max = box;
		}
	}
	if (i - 1 >= 0) {
		if (space[i - 1][j] != -1) {
			box = search(i - 1, j, score, count + 1);
			if (s_max < box)
				s_max = box;
		}
	}
	if (j - 1 >= 0) {
		if (space[i][j - 1] != -1) {
			box = search(i, j - 1, score, count + 1);
			if (s_max < box)
				s_max = box;
		}
	}
	if (i + 1 < 501 && j + 1 < 501) {
		if ((space[i + 1][j] == -1 || space[i][j + 1] == -1)) {
			if (space[i + 1][j + 1] != -1) {	
				box = search(i + 1, j + 1, score, count + 1);
				if (s_max < box)
					s_max = box;
			}
		}
	}
	if (j + 1 < 501 && i - 1 > -1) {
		if ((space[i][j + 1] == -1 || space[i - 1][j] == -1)) {
			if (space[i - 1][j + 1] != -1) {
				box = search(i - 1, j + 1, score, count + 1);
				if (s_max < box)
					s_max = box;
			}
		}
	}
	if (i + 1 <501 && j - 1 > -1) {
		if (space[i][j - 1] == -1 || space[i + 1][j] == -1) {
			if (space[i + 1][j - 1] != -1) {
				box = search(i + 1, j - 1, score, count + 1);
				if (s_max < box)
					s_max = box;
			}
		}
	}
	if (j - 1 >= 0 && i - 1 >= 0) {
		if (space[i - 1][j] == -1 || space[i][j - 1] == -1) {
			if (space[i - 1][j - 1] != -1) {
				box = search(i - 1, j - 1, score, count + 1);
				if (s_max < box)
					s_max = box;
			}
		}
	}
	space[i][j] = empty_box;
	return s_max;
}
int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &space[i][j]);
		}
	}

	int empty_box = 0;
	int box = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			box=search(i, j, empty_box, 0);
			if (box > max)
				max = box;
		}
	}
	printf("%d", max);
	return 0;
}