백준 14500. 테트로미노

알고리즘 기초 문제 중 브루트포스 기초 문제(500)

테트로미노

1. 간단 설명

---

NxM 맵에 각 칸에 정수가 하나씩 쓰여져있다

테트로미노 하나를 놓아서, 그 테트로미노가 놓인 칸에 쓰여있는 수들의 합이 최대가 되는 경우를 구하는 문제

2. 예시

---

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
에서는 

4 5 6
4

를 고르는 경우가 19로 가장 크다

이런식으로 블록을 놓아서 가장 큰 합을 찾는 문제

3. 알고리즘

---

직접 테트로미노를 만들고, 대칭 회전시켜서

이 테트로미노가 밟는 칸의 숫자를 모두 더한다

DFS로도 풀 수 있지만, T 모양은 별도로 처리해주어야하기 때문에

간단히 모든 모양을 직접 구현하여 풀었다

막대기와 같은 테트로미노는 회전하나 대칭하나 같기 때문에

40(5개 * 대칭 2개 * 회전 4개)개의 테트로미노를 모두 구현할 필요 없이, 총 19개만 구현하면 된다

1. N과 M을 입력받는다
2. 최대값을 0으로 초기화
3. 0,0부터 시작하여 각 칸에 19개의 테트로미노를 하나씩 놓아본다
4. 해당 칸의 숫자를 더한 수가 최대값이라면 갱신함
5. 최대값 출력 후 종료

4. 소스코드

---

블럭의 좌표를 기록하는 방식

이 방식이 메모리 효율 및 성능적에서 낫다

#include <iostream>

using namespace std;

int n, m;
int map[501][501];

// 19개 블록에 대해 y,x 좌표를 저장
// 회전 및 대칭에 대해 중복은 제거
int tetrominon[19][4][2] = { 
	// 막대(2개)
	{ {0,0}, {0,1}, {0,2}, {0,3} },
	{ {0,0}, {1,0}, {2,0}, {3,0} },
	// 네모
	{ {0,0}, {0,1}, {1,0}, {1,1} },
	// L
	{ {0,0}, {1,0}, {1,1}, {1,2} },
	{ {0,0}, {0,1}, {1,0}, {2,0} },
	{ {0,0}, {0,1}, {0,2}, {1,2} },
	{ {0,0}, {1,0}, {2,0}, {2,-1} },
	{ {0,0}, {0,1}, {0,2}, {-1,2} },
	{ {0,0}, {1,0}, {2,0}, {2,1} },
	{ {0,0}, {0,1}, {0,2}, {1,0} },
	{ {0,0}, {0,1}, {1,1}, {2,1} },
	// Z
	{ {0,0}, {0,1}, {-1,1}, {-1,2} },
	{ {0,0}, {1,0}, {1,1}, {2,1} },
	{ {0,0}, {0,1}, {1,1}, {1,2} },
	{ {0,0}, {1,0}, {1,-1}, {2,-1}  },
	// T
	{ {0,0}, {0,1}, {0,2}, {-1,1} },
	{ {0,0}, {0,1}, {0,2}, {1,1} },
	{ {0,0}, {1,0}, {2,0}, {1,1} },
	{ {0,0}, {1,0}, {2,0}, {1,-1} },
};


void Input() {
	cin >> n >> m;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> map[y][x];
		}
	}

}

int main() {
	// freopen_s(new FILE*, "test.txt", "r", stdin);
	Input();

	// 값 찾기
	int max_value = 0;
	
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			// 블럭 19개에 대해 확인
			for (int i = 0; i < 19; i++) {
				int sum = 0; 
				for (int j = 0; j < 4; j++) { // 블럭은 4칸
					int dy = y + tetrominon[i][j][0];
					int dx = x + tetrominon[i][j][1];

					if (dy < 0 || dx < 0 || dy >= n || dx >= m) continue; // 하나라도 밖으로 튀어나가면 정지

					sum += map[dy][dx];
				}
				if (sum > max_value) {
					max_value = sum;
				}
			}

		}
	}
	cout << max_value;

	return 0;
}

블럭을 시각화하기 위해 3차원 배열로 놓은 방식

#include <iostream>
#include <algorithm>

#define BLOCK 19

using namespace std;

int tetromino[BLOCK][4][4] = {
	// 막대기
	{
		1,1,1,1,
		0,0,0,0,
		0,0,0,0,
		0,0,0,0
	},
	{
		1,0,0,0,
		1,0,0,0,
		1,0,0,0,
		1,0,0,0,
	},
	// 네모
	{
		1,1,0,0,
		1,1,0,0,
		0,0,0,0,
		0,0,0,0,
	},
	// L
	{
		1,1,1,0,
		1,0,0,0,
		0,0,0,0,
		0,0,0,0
	},
	{
		1,1,0,0,
		0,1,0,0,
		0,1,0,0,
		0,0,0,0
	},
	{
		0,0,1,0,
		1,1,1,0,
		0,0,0,0,
		0,0,0,0
	},
	{
		1,0,0,0,
		1,0,0,0,
		1,1,0,0,
		0,0,0,0
	},
	// L 대칭
	{
		1,1,0,0,
		1,0,0,0,
		1,0,0,0,
		0,0,0,0
	},
	{
		1,0,0,0,
		1,1,1,0,
		0,0,0,0,
		0,0,0,0
	},
	{
		0,1,0,0,
		0,1,0,0,
		1,1,0,0,
		0,0,0,0
	},
	{
		1,1,1,0,
		0,0,1,0,
		0,0,0,0,
		0,0,0,0
	},
	// S
	{
		1,0,0,0,
		1,1,0,0,
		0,1,0,0,
		0,0,0,0
	},
	{
		0,1,1,0,
		1,1,0,0,
		0,0,0,0,
		0,0,0,0
	},
	// S 대칭
	{
		1,1,0,0,
		0,1,1,0,
		0,0,0,0,
		0,0,0,0
	},
	{
		0,1,0,0,
		1,1,0,0,
		1,0,0,0,
		0,0,0,0
	},
	// T
	{
		1,1,1,0,
		0,1,0,0,
		0,0,0,0,
		0,0,0,0
	},
	{
		0,1,0,0,
		1,1,0,0,
		0,1,0,0,
		0,0,0,0
	},
	{
		0,1,0,0,
		1,1,1,0,
		0,0,0,0,
		0,0,0,0
	},
	{
		1,0,0,0,
		1,1,0,0,
		1,0,0,0,
		0,0,0,0
	}
};

int N, M;
int map[510][510];

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
		}
	}

	int max_val = 0;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {

			for (int k = 0; k < BLOCK; k++) {
				int cur = 0;
				for (int i = 0; i < 4; i++) {
					for (int j = 0; j < 4; j++) {
						if (tetromino[k][i][j] != 0) {
							cur += map[y + i][x + j];
						}
					}
				}
				max_val = max(max_val, cur);
			}
			
		}
	}

	cout << max_val;

	return 0;
}