[백준 14500] 테트로미노

1x1 4개를 이어 붙인다. 총 5가지가 있다.

 

 

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

따라서 5가지가 아니라 파랑색은 2가지 노란색 1가지 오랜지색은 8가지 연두색은 4가지 보라색은 4가지이다.

---

총 그래서 19가지

이 경우를 모두 할 수 있도록 미리 방향배열을 만들고나서

이 방향배열들을 모두 실행하도록하면 19*4 = 76 그리고 이 76번의 연산이 모든 배열에서 실행되므로 500\*500\*76 = 약 40000 500 => 20000000 약 2천만번의 연산이 일어난다. 시간제한은 2초 약 2억번의 연산을 감당할 수 있으므로 충분히 가능하다.

그래서 브루드포스로 무식하게 풀어도 가능한 문제이다. 그렇게 풀도록 하자. (딱히 다른 방법은 생각이 안난다)

사실 시작부분은 이미 시작부분이기 때문에 {0,0}의 연산을 빼면 연산이 훨씬 더 줄어들수있다!

 

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int arr[500][500];
int big = 0;
pair<int,int> yellow[4] = {{0,0},{0,1},{1,0},{1,1}};

pair<int, int> blue[2][4] = { {{0,0},{0,1},{0,2},{0,3} }, {{0,0},{1,0},{2,0},{3,0}} };

pair<int, int> orange[8][4] = { {{0,0},{1,0},{2,0},{2,1}} , {{0,0},{0,1},{0,2},{1,0}} , {{0,0},{0,1},{1,1},{2,1}},{{0,0},{0,1},{0,2},{-1,2}},{{0,0},{0,1},{-1,1},{-2,1}},
	{{0,0},{0,1},{0,2},{1,2}} , {{0,0},{0,1},{1,0},{2,0}} , {{0,0},{1,0},{1,1},{1,2}}
};

pair<int, int> green[4][4] = {
	{{0,0},{1,0},{1,1},{2,1}}   ,  {{0,0},{0,1},{1,0},{1,-1}} , {{0,0},{1,0},{1,-1},{2,-1}} , {{0,0}, {0,1}, {1,1},{1,2}}
};

pair<int, int> bora[4][4] = {
	{{0,0}, {0,1},{0,2},{1,1}}, {{0,0},{1,0},{2,0},{1,-1}} , {{0,0},{1,0},{1,1},{1,-1}} , {{0,0},{1,0},{2,0},{1,1}}

};


bool validCheck(int n, int m)
{
	return n >= 0 && n < N&& m >= 0 && m < M;
}

void calc(int n, int m)
{
	int x = 0; 
	int y = 0;
	int sum = 0;
	//yellow 
	for (int i = 0; i < 4; i++)
	{

		x = n + yellow[i].first;
		y = m + yellow[i].second;

		if (validCheck(x, y))
		{
			sum += arr[x][y];
		}
		else {//한번이라도 유효성 통과 못하면 이건 끝
			sum = 0;
			break;
		}
	}
	big = max(big, sum);
	sum = 0;

	//blue
	for (int j = 0; j < 2; j++)
	{
		for (int i = 0; i < 4; i++)
		{

			x = n + blue[j][i].first;
			y = m + blue[j][i].second;

			if (validCheck(x, y))
			{
				sum += arr[x][y];
			}//한번이라도 유효성 통과 못하면 이건 끝
			else {
				sum = 0;
				break;
			}
		}
		big = max(big, sum);

		sum = 0;
	}
	sum = 0;
	//orange
	for (int j = 0; j < 8; j++)
	{
		for (int i = 0; i < 4; i++)
		{

			x = n + orange[j][i].first;
			y = m + orange[j][i].second;

			if (validCheck(x, y))
			{
				sum += arr[x][y];
			}//한번이라도 유효성 통과 못하면 이건 끝
			else {
				sum = 0;
				break;
			}
		}
		big = max(big, sum);

		sum = 0;
	}
	sum = 0;


	//green
	for (int j = 0; j < 4; j++)
	{
		for (int i = 0; i < 4; i++)
		{

			x = n + green[j][i].first;
			y = m + green[j][i].second;

			if (validCheck(x, y))
			{
				sum += arr[x][y];
			}//한번이라도 유효성 통과 못하면 이건 끝
			else {
				sum = 0;
				break;
			}
		}
		big = max(big, sum);

		sum = 0;
	}
	sum = 0;

	//bora
	for (int j = 0; j < 4; j++)
	{
		for (int i = 0; i < 4; i++)
		{

			x = n + bora[j][i].first;
			y = m + bora[j][i].second;

			if (validCheck(x, y))
			{
				sum += arr[x][y];
			}//한번이라도 유효성 통과 못하면 이건 끝
			else {
				sum = 0;
				break;
			}
		}
		big = max(big, sum);

		sum = 0;
	}
	sum = 0;
}


int main()
{
	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++)
		{
			
			calc(i, j);
			
		}
	}


	cout << big;


}

---

 

다른풀이

 

테트로미노를 회전이나 대칭을 시켜도 되기 때문에 'ㅗ' 모양을 빼고는 모두 DFS(Depth First Search)로 표현할 수 있습니다

그래서 visited[n][m]의 방문표시를 잘 활용해서 4칸만큼 이동하면 됩니다.(미리미리 진행한 횟수를 저장)

int DFS(int y, int x, int cnt)

{

        if (cnt == 4)

                 return cell[y][x];

       

        int sum = 0;

 

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M && !visited[nextY][nextX])

                 {

                         visited[nextY][nextX] = true;

                         sum = max(sum, cell[y][x] + DFS(nextY, nextX, cnt + 1));

                         visited[nextY][nextX] = false; //꼭 처리해줘야한다

                 }

        }

        return sum;

}

그리고 ㅗ는 dfs로 판별이 불가능하므로 직접계산