백준 14500 테트로미노 C언어- Brute force + DFS

테트리스에서 나오는 블록들을 NxM 종이 위에 올리는데 종이에 적힌 값이 가장 크도록 만들고 싶다.

종이의 크기는 최대 500x500 이므로 25만 정도이므로 N * 400 = 1억이므로 하나의 좌표당 최대 

400 개의 연산을 할 수 있다고 보면 될 것 같다.

 

위 그림에서는 5가지의 형태가 그려져있다. 

실제로 종이에 올릴 때는 블록들을 돌리거나 뒤집을 수 있으므로 각 도형에 대해 모두 수행해봐야한다.

ㅏㅓㅗㅜ 모양을 제외한 나머지 블록들은 xy 좌표 기준으로 3번의 dfs를 수행하여 고르면 된다.

하지만 ㅏㅓㅗㅜ 는 dfs로 탐색하기 힘드므로 하드하게 코딩하는 방식을 썼다.

 

구현 방식은 다음과 같다.

1. DFS 방식으로 특정 좌표 x,y 에서 탐색하여 블록을 만들어 그 때의 값을 구한다.

2. 같은 좌표에서 ㅏㅓㅗㅜ 일 때 값을 구한다.

3. 둘 중 더 큰 값을 취한다.

4. x,y 좌표를 이동시킨다.

5. 종이 전체를 탐색한다.

 

밑의 코드에서 makeblock 은 dfs방식으로 블록을 만드는 함수이고, 

carblock 은 ㅏㅓㅗㅜ 모양의 블록의 값을 하드하게 구한 함수이다.

 

전체코드

#include <stdio.h>

int N, M;
int ans;
int MAP[501][501];
int visited[501][501];

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

int carblock(int y, int x) {
	int ans = MAP[y][x];
	int max = ans;
	if (x+2 < M ) {
		// ㅜ
		if (y + 1 < N) {
			ans += MAP[y + 1][x + 1] + MAP[y][x + 1] + MAP[y][x + 2];
			max = ans > max ? ans : max;
		}
		// ㅗ
		if (y - 1 >= 0) {
			ans = MAP[y][x] + MAP[y - 1][x + 1] + MAP[y][x + 1] + MAP[y][x + 2];
			max = ans > max ? ans : max;
		}
	}
	if ( y + 2 < N) {
		// ㅓ
		if (x - 1 >= 0) {
			ans = MAP[y][x] + MAP[y + 1][x - 1] + MAP[y + 1][x] + MAP[y + 2][x];
			max = ans > max ? ans : max;
		}
		//ㅏ
		if (x + 1 < M) {
			ans = MAP[y][x] + MAP[y + 1][x] + MAP[y + 2][x] + MAP[y + 1][x + 1];
			max = ans > max ? ans : max;
		}

	}
	return max;
}

int makeblock(int y, int x, int num, int sum) {
	if (num == 0) {

		//printf("CUR y: %d x : %d\n", y, x);
		if (ans < sum) ans = sum;
		return 0;
	}
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= N || ny < 0 || nx < 0 || nx >= M) continue;
		if (!visited[ny][nx]) {
			visited[ny][nx] = 1;
			makeblock(ny, nx, num - 1, sum + MAP[ny][nx]);
			visited[ny][nx] = 0;
		}
	}
	return 0;
}

int sol() {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			//printf("IN Y : %d X : %d\n", i, j);
			visited[i][j] = 1;
			makeblock(i, j, 4-1, MAP[i][j]);
			visited[i][j] = 0;
			int tmp = carblock(i, j);
			ans = ans>tmp?ans:tmp;
		}
	}
	return 0;
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &MAP[i][j]);
		}
	}
	sol();
	printf("%d", ans);
}