[백준] 14500번 - 테트로미노

링크

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

14500번: 테트로미노

풀이

정사각형 4개가 연결되어 만들어진 도형에 들어가는 수의 합중 가장 큰 값을 구하는 문제 이다.

 

처음에는 모든 좌표를 next_permutation으로 돌려서 좌표평면에 있는 4개의 좌표를 25000C4의 조합으로 만들어 확인 하려 하였으나. 경우의 수가 너무 많았다. 

 

그래서 정사각형 4개가 붙어 있는 경우만을 이용 하기로 하였다.

 

붙어있는 정사각형을 탐색하기 위해서는 DFS를 이용하기로 하였다. 그런데 DFS만으로는 테트로미노의 조건을 충족하는 모든 도형을 찾아 낼 수는 없었다.

 

왼쪽의 그림과 같이 4개의 도형은 DFS 탐색으로 찾아낼 수 있지만

 

나머지 1개 ㅗ 도형은 DFS 탐색으로 찾아 낼 수가 없었다.

 

 

 

그래서 도형 4개는 DFS 탐색으로 도형에 들어가는 수의 합 중 가장 큰 값을 찾아 내었고

 

DFS로 찾을 수 없는 도형은 직접 배열을 만들어 슬라이딩 윈도우처럼 비교를 하여 큰 값을 찾아 내도록 하였다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>

#define SIZE 510
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

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

int board[SIZE][SIZE];
bool visited[SIZE][SIZE];

int chul[4][9][9] =
{
	{
		{0,1,0},
		{1,1,1},
		{0,0,0}
	},
	{
		{ 1,1,1 },
		{ 0,1,0 },
		{ 0,0,0 }
	},
	{
		{ 1,0,0 },
		{ 1,1,0 },
		{ 1,0,0 }
	},
	{
		{ 0,1,0 },
		{ 1,1,0 },
		{ 0,1,0 }
	},
};

int N, M;
int res = 0;

int check() {
	int cost = 0;
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			for (int d = 0; d < 4; d++) {
				sum = 0;
				for (int di = 0; di < 3; di++) {
					for (int dj = 0; dj < 3; dj++) {
						sum += chul[d][di][dj] * board[i + di][j + dj];
					}
				}
				cost = max(sum, cost);
			}
		}
	}
	return cost;
}
void dfs(int h_x, int h_y, int sum, int cnt) {
	if (cnt == 4) {
		res = max(res, sum);
		return;
	}

	sum += board[h_x][h_y];
	visited[h_x][h_y] = true;

	for (int d = 0; d < 4; d++) {
		int n_x = h_x + dx[d];
		int n_y = h_y + dy[d];

		if (n_x<1 || n_x >N || n_y<1 || n_y>M)
			continue;;

		if (visited[n_x][n_y] == true)
			continue;

		dfs(n_x, n_y, sum, cnt + 1);
	}
	visited[h_x][h_y] = false;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	 cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			dfs(i, j, 0, 0);
		}
	}

	res = max(res, check());
	cout << res;
}