[백준] C++ 테트로미노(1450)

네모난 종이에 숫자가 써져 있다. 테트로미노를 종이 위에 올려놓았을 때 합의 최댓값을 찾는 문제이다.

테트로미노의 회전, 대칭을 허용한다.

나는 이 문제를 처음에 보았을 때 DFS를 사용해서 모든 경우의 수를 4칸씩 이동시켰다. 간단하게 DFS로 깊이 있게 들어가니 

이 도형에 대해서는 탐색을 하지 못하는 문제가 발생하였다.

그래서 DFS를 사용한 후 저 도형에 대해 탐색하는 로직만 추가로 작성해 주었다.

위와 같은 도형이 나오는 경우의 수는 4가지이다

위, 아래로 솟아있거나 좌, 우로 솟아있는 경우이다.

 

둘 다 범위를 초과함

한 곳을 중심으로 잡고 상, 하, 좌, 우로 범위를 확인해 본다.

만약 (상, 하)중에(OR) 하나라도 범위를 초과하고(AND) (좌, 우)중에(OR) 하나라도 범위를 초과하면

그곳에는 저 도형을 놓지 못한다.

(상, 하)가 깔끔하거나 (좌, 우)가 깔끔하거나 둘 중에 하나는 깔끔해야 한다.

(상)만 범위를 초과함.

상,하,좌,우 깔끔함.

 

#include <iostream>

using namespace std;

int arr[1001][1001];

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

void DFS(int x, int y, int dir, int count, int sum);
void Search(int x, int y);
int N = 0;
int M = 0;
int max1 = 0;

int main(void)
{

	cin >> N >> M;

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

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			DFS(i, j, 0, 1, arr[i][j]);//상 하 좌 우  1, -1, -2, 2
			Search(i, j);
		}
	}

	cout << max1;
	return 0;
}

void DFS(int x, int y, int dir, int count, int sum)
{
	if (count < 4)
	{
		for (int i = 0; i < 4; i++)
		{
			if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] < N && y + dy[i] < M)
			{
				if (dir != (-d[i]))//이전에 왔던 방향은 이동하지 않겠다.
				{
					DFS(x + dx[i], y + dy[i], d[i], count + 1, sum + arr[x + dx[i]][y + dy[i]]);
				}
			}
		}
	}
	else
	{
		if (sum > max1)
		{
			max1 = sum;
		}
	}

}

void Search(int x, int y)// ㅗ 모양 도형을 찾는 함수
{
	int sig[4] = { 0 };
	for (int i = 0; i < 4; i++)
	{
		if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] < N && y + dy[i] < M)//상, 하, 좌, 우 범위를 초과하는지 확인.
		{
			sig[i] = 0;
		}
		else
		{
			sig[i] = 1;
		}
	}

	if (sig[0] == 0 && sig[1] == 0)//상, 하가 깔끔하고
	{
		int sum = arr[x][y] + arr[x - 1][y] + arr[x + 1][y];
		if (sig[2] == 1)//좌가 범위를 초과하면
		{
			//왼쪽만 뺌.
			sum += arr[x][y + 1];
			if (sum > max1)
			{
				max1 = sum;
			}
		}
		else if (sig[3] == 1)//우가 범위를 초과하면
		{
			//오른쪽만 뻄
			sum += arr[x][y - 1];
			if (sum > max1)
			{
				max1 = sum;
			}
		}
		else//둘다 초과하지 않는다면
		{
			int temp1 = sum + arr[x][y + 1];
			int temp2 = sum + arr[x][y - 1];

			if (temp1 > max1)
			{
				max1 = temp1;
			}
			if (temp2 > max1)
			{
				max1 = temp2;
			}
			//둘다 봄.
		}
	}
	if (sig[2] == 0 && sig[3] == 0)
	{
		int sum = arr[x][y] + arr[x][y - 1] + arr[x][y + 1];
		if (sig[0] == 1)
		{
			//위만 뺌
			sum += arr[x - 1][y];
			if (sum > max1)
			{
				max1 = sum;
			}
		}
		else if (sig[1] == 1)
		{
			//아래만 뺌
			sum += arr[x + 1][y];
			if (sum > max1)
			{
				max1 = sum;
			}
		}
		else
		{
			int temp1 = sum + arr[x - 1][y];
			int temp2 = sum + arr[x + 1][y];

			if (temp1 > max1)
			{
				max1 = temp1;
			}
			if (temp2 > max1)
			{
				max1 = temp2;
			}
			//둘다 봄.
		}
	}

}