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

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

14500번: 테트로미노

풀이과정

1. 4개의 정사각형을 이어붙인 모양으로 해당 구역의 최댓값을 구하는 문제이다.

 

위의 사진과 같은 형태를 이루는데 회전이나 대칭 또한 체크해야한다.

 

2. bfs를 이용하여 depth가 4인 경우를 따지게 되면, 보라색을 제외한 모든 경우가 나오게 된다.

 

3. 보라색의 형태를 이루는 모양 따로 체크를 해주면 된다.

 

 

 

결과

 

소스코드(c++)

#include <stdio.h>

int answer;
int map[500][500];
int visited[500][500];
int N, M;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int dx2[4][3] = { {1, 2, 1}, {1, 2, 1}, {0, 0, -1}, {0, 0, 1} };
int dy2[4][3] = { {0, 0, 1}, {0, 0,-1}, {1, 2,  1}, {1, 2, 1} };
void bfs(int x, int y, int depth, int sum)
{
	if (depth >= 4) {
		if (answer < sum) {
			answer = sum;
		}
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= M || ny >= N || visited[ny][nx] == 1) continue;
		visited[ny][nx] = 1;
		bfs(nx, ny, depth + 1, sum + map[ny][nx]);
		visited[ny][nx] = 0;
	}
}

void remainTetris(int x, int y)
{
	int sum = 0;
	for(int i = 0; i < 4; i++) {
		sum = map[y][x];
		for (int j = 0; j < 3; j++) {
			int nx = x + dx2[i][j];
			int ny = y + dy2[i][j];
			if (nx < 0 || ny < 0 || nx >= M || ny >= N) break;
			sum += map[ny][nx];
		}
		if (answer < sum) {
			answer = sum;
		}
	}
}

void solution()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = 1;
			bfs(j, i, 1, map[i][j]);
			remainTetris(j, i);
			visited[i][j] = 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]);
		}
	}

	solution();
	printf("%d\n", answer);
}