[Brute Force - 재귀] 테트로미노

 

예제 입력 1

5 5

1 2 3 4 5

5 4 3 2 1

2 3 4 5 6

6 5 4 3 2

1 2 1 2 1

예제 출력 1

19

예제 입력 2

4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

예제 출력 2

20

예제 입력 3

4 10

1 2 1 2 1 2 1 2 1 2

2 1 2 1 2 1 2 1 2 1

1 2 1 2 1 2 1 2 1 2

2 1 2 1 2 1 2 1 2 1

예제 출력 3

7

 

- 회전/대칭이 가능하므로 아래 도형을 제외한 나머지는 임의의 1칸에서 시작해 3개의 칸을 연속해서 방문한 형태이다. 

- 아래 도형만 직접 처리하고, 나머지는 재귀로 처리할 수 있다.

- Brute Force와 재귀함수의 차이점은 아래 처럼 방문후에 체크를 빼주어야 한다는 것이다.

 

	visited[r][c] = true;
	
    ....

	visited[r][c] = false;

 

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

 

#include <stdio.h>

#define MAX_SIZE (500)
#define MIN_VALUE (-2147483648)

#define MAX(a,b) ((a)>(b)?(a):(b))

int R, C;
int map[MAX_SIZE][MAX_SIZE] = { 0, };
bool visited[MAX_SIZE][MAX_SIZE] = { false, };

int dR[4] = { -1, 1, 0, 0 };
int dC[4] = { 0, 0, -1, 1 };

int maxResult = MIN_VALUE;

bool isInBoundary(int r, int c)
{
	return (r >= 0) && (r < R) && (c >= 0) && (c < C);
}

void go(int r, int c, int cnt, int curValue)
{
	if (cnt == 4)
	{
		maxResult = MAX(maxResult, curValue);
		return;
	}

	visited[r][c] = true;
	curValue += map[r][c];

	for (int i = 0; i < 4; i++)
	{
		int newR = r + dR[i];
		int newC = c + dC[i];

		if (!isInBoundary(newR, newC)) continue;

		if (!visited[newR][newC])
		{
			go(newR, newC, cnt + 1, curValue);
		}
	}

	visited[r][c] = false;
}

int main(void)
{
	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			scanf("%d", &map[i][j]);

		}
	}

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			go(i, j, 0, 0);

			//(o)
			// oo
			// o
			if (i + 2 < R && j + 1 < C)
			{
				int nowResult = map[i][j] + map[i + 1][j] + map[i + 2][j] + map[i + 1][j + 1];
				maxResult = MAX(maxResult, nowResult);
			}

			//   o
			//(o)oo
			if (i - 1 >= 0 && j + 2 < C)
			{
				int nowResult = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i-1][j + 1];
				maxResult = MAX(maxResult, nowResult);
			}

			// (o)oo
			//    o
			if (i + 1 < R && j + 2 < C)
			{
				int nowResult = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i + 1][j + 1];
				maxResult = MAX(maxResult, nowResult);
			}

			//  (o)
			//  oo
			//   o
			if (i + 2 < R && j - 1 >= 0)
			{
				int nowResult = map[i][j] + map[i + 1][j - 1] + map[i + 1][j] + map[i + 2][j];
				maxResult = MAX(maxResult, nowResult);
			}
		}
	}
	
	printf("%d\n", maxResult);
	

	return 0;
}