5개의 모형에 대해 회전하는 모든 경우의 수를 배열에 저장하여 시뮬레이션 돌렸다.
사실 풀면서도 이건 아닌 거 같다는 생각이 들었지만,, 별다른 방법이 생각나지 않았고 문제를 풀긴 했다.
위 그림처럼 ㅜ 모양을 제외한 나머지 블럭은 depth가 3인 DFS로 풀면 쉽게 풀 수 있는 거였다!
DFS의 인자로 x좌표, y좌표, count, sum 을 주면 될 것 같다.
ㅜ의 경우 내가 푼 것처럼 풀이를 작성하면 될 것 같다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N, M, rst;
int map[500][500];
int dx[] = { 0, -1, 0, 1, 1};
int dy[] = { 1, 0, -1, 0, 1 };
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
rst = 0;
}
int is_range(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < M) return true;
return false;
}
int one(int x, int y, int cnt) {
const int case_num = 2;
const int idx = 3;
int vec[case_num][idx] = { {0, 0, 0}, {3, 3, 3} };
int nx, ny, sum, rst = 0;
bool flag;
int xx = x, yy = y;
for (int i = 0; i < case_num; i++) {
flag = true;
sum = cnt;
x = xx, y = yy;
for (int j = 0; j < idx; j++) {
nx = x + dx[vec[i][j]];
ny = y + dy[vec[i][j]];
x = nx; y = ny;
if (is_range(nx, ny)) {
sum += map[nx][ny];
}
else {
flag = false;
break;
}
}
if (flag) rst = max(sum, rst);
}
return rst; // 놓을 수 없는 경우 0을 리턴 근데 그럴 경우 없음
}
int two(int x, int y, int cnt) {
const int case_num = 1;
const int idx = 3;
int vec[case_num][idx] = { {0, 3, 4} };
int nx, ny, sum, rst = 0;
bool flag;
int xx = x, yy = y;
for (int i = 0; i < case_num; i++) {
flag = true;
sum = cnt;
x = xx, y = yy;
for (int j = 0; j < idx; j++) {
nx = x + dx[vec[i][j]];
ny = y + dy[vec[i][j]];
if (is_range(nx, ny)) {
sum += map[nx][ny];
}
else {
flag = false;
break;
}
}
if (flag) rst = max(sum, rst);
}
return rst;
}
int three(int x, int y, int cnt) {
const int case_num = 8;
const int idx = 3;
int vec[case_num][idx] = { {3,3,0}, {3,3,2}, {0,3,3}, {2,3,3}, {3,2,2}, {3, 0, 0}, {0, 0, 3}, {2, 2, 3} };
int nx, ny, sum, rst = 0;
bool flag;
int xx = x, yy = y;
for (int i = 0; i < case_num; i++) {
flag = true;
sum = cnt;
x = xx, y = yy;
for (int j = 0; j < idx; j++) {
nx = x + dx[vec[i][j]];
ny = y + dy[vec[i][j]];
x = nx; y = ny;
if (is_range(nx, ny)) {
sum += map[nx][ny];
}
else {
flag = false;
break;
}
}
if (flag) rst = max(sum, rst);
}
return rst;
}
int four(int x, int y, int cnt) {
const int case_num = 4;
const int idx = 3;
int vec[case_num][idx] = { {3,0,3}, {3,2,3},{0,3,0},{2,3,2} };
int nx, ny, sum, rst = 0;
bool flag;
int xx = x, yy = y;
for (int i = 0; i < case_num; i++) {
flag = true;
sum = cnt;
x = xx, y = yy;
for (int j = 0; j < idx; j++) {
nx = x + dx[vec[i][j]];
ny = y + dy[vec[i][j]];
x = nx; y = ny;
if (is_range(nx, ny)) {
sum += map[nx][ny];
}
else {
flag = false;
break;
}
}
if (flag) rst = max(sum, rst);
}
return rst;
}
int five(int x, int y, int cnt) {
const int case_num = 4;
const int idx = 3;
int vec[case_num][idx] = { {0,3,0}, {3,2,3}, {3,2,0},{3,0,3} };
int nx, ny, sum, rst = 0;
int px, py;
bool flag;
for (int i = 0; i < case_num; i++) {
flag = true;
sum = cnt;
for (int j = 0; j < idx; j++) {
if (j == 0) {
nx = x + dx[vec[i][j]];
ny = y + dy[vec[i][j]];
px = nx; py = ny;
}
else {
nx = px + dx[vec[i][j]];
ny = py + dy[vec[i][j]];
}
if (is_range(nx, ny)) {
sum += map[nx][ny];
}
else {
flag = false;
break;
}
}
if (flag) rst = max(sum, rst);
}
return rst;
}
void test(int x, int y, int cnt) {
rst = max(rst, one(x, y, cnt));
rst = max(rst, two(x, y, cnt));
rst = max(rst, three(x, y, cnt));
rst = max(rst, four(x, y, cnt));
rst = max(rst, five(x, y, cnt));
}
void solve() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
test(i, j, map[i][j]);
}
}
}
int main() {
input();
solve();
cout << rst << endl;
}
찾아보니 DFS 문제라는데 나는 하드코딩으로 냅따 품.. 최적화란 없다.. 다시 풀어봐야겠다.