Problem Solving/BOJ
[BOJ] #14500 _ 테트로미노
Grini
2019. 10. 20. 23:16
[테트로미노] https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
dfs를 이용하여 모든 경우의 수를 고려하여 최대 값을 구하였다.
모든 좌표를 시작점으로 두고, 5가지의 각 테트로미노를 놓아 값을 구한 후 최대 값을 갱신해주었다.
단, 'ㅗ' 는 dfs를 이용하여 값을 구할 수 없기에 따로 하드코딩으로 값을 얻었다.
[ 소스 코드 ]
#include <cstdio>
#include <algorithm>
#define MAX 500
using namespace std;
int dx[] = { 0, 0, -1, 1 }, dy[] = { -1, 1, 0, 0 };
int N, M, max_val = 0;
int map[MAX][MAX], chk[MAX][MAX];
void solve(int cnt, int res, int y, int x);
void getUval(int y, int x);
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]);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
chk[i][j] = 1;
getUval(i, j);
solve(1, map[i][j], i, j);
chk[i][j] = 0;
}
}
printf("%d\n", max_val);
return 0;
}
void solve(int cnt, int res, int y, int x) {
int tmp_x, tmp_y;
if (cnt + 1 > 4) {
max_val = max(max_val, res);
return;
}
for (int i = 0; i < 4; i++) {
tmp_x = x + dx[i];
tmp_y = y + dy[i];
if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) continue;
if (chk[tmp_y][tmp_x]) continue;
chk[tmp_y][tmp_x] = 1;
solve(cnt + 1, res + map[tmp_y][tmp_x], tmp_y, tmp_x);
chk[tmp_y][tmp_x] = 0;
}
}
void getUval(int y, int x) {
int result;
if (x < M - 1 && y < N - 2) {
result = map[y][x] + map[y + 1][x] + map[y + 1][x + 1] + map[y + 2][x]; // ㅏ
max_val = max(max_val, result);
}
if (x < M - 2 && y < N - 1) {
result = map[y][x] + map[y][x + 1] + map[y + 1][x + 1] + map[y][x + 2]; // ㅜ
max_val = max(max_val, result);
}
if (x > 0 && y < N - 2) {
result = map[y][x] + map[y + 1][x] + map[y + 1][x - 1] + map[y + 2][x]; // ㅓ
max_val = max(max_val, result);
}
if (x < M - 2 && y > 0) {
result = map[y][x] + map[y][x + 1] + map[y - 1][x + 1] + map[y][x + 2]; // ㅗ
max_val = max(max_val, result);
}
}