처음에 문제를 보고 DFS로 모든 경우의 수를 확인해야 겠다고 생각했습니다. (4 <= N, M <= 500이기 때문에 O(n^2)의 시간복잡도를 가지고 있다고 하면 250000, DFS의 깊이도 4밖에 되지 않음.)
문제를 푼 후 테스트 케이스를 돌렸을 때 예제 3의 답이 틀렸습니다. 이유는 보라색의 테트로미노는 DFS탐색으로 만들기 불가하였기 때문입니다.
처음부터 다시 문제를 접근해야 할까 생각했지만 문제에서 테트로미노는 다음과 같은 5가지라고 명시가 되어있고 예외 케이스는 한가지 이기 때문에 한 테트로미노에 대해서는 따로 계산해서 접근해 보았습니다.
Brute-force + DFS
한 칸 한 칸에 대해서 DFS기반으로 모든 테트로미노(한 케이스 제외)를 두어 놓은 칸에 쓰여 있는 수를 구하고 DFS로 구하지 못하는 한 케이스에 대해서는 따로 계산.
#include <iostream>
#include <vector>
using namespace std;
int T;
int N, M;
int answer;
vector<vector<int>> table;
vector<vector<int>> visit;
int i, j;
// 가려는 칸으로 이동할 수 있는지 판단
int go(int x, int y) {
if(x >= 0 && x < N && y >=0 && y < M && (visit[x][y] == 0)) {
return 1;
}
else {
return 0;
}
}
// DFS 기반 solver
void solver(int x, int y, int cnt, int point) {
int cp = point + table[x][y];
visit[x][y] = 1;
// 4칸의 테트로미노 완성되고 값이 최댓값보다 크면 갱신.
if(cnt == 4) {
if(cp > answer)
answer = cp;
}
// 4칸이 만족이 되지 않으면 다음칸으로 이동.
else {
if(go(x + 1, y)) {
solver(x + 1, y, cnt + 1, cp);
}
if(go(x - 1, y)) {
solver(x - 1, y, cnt + 1, cp);
}
if(go(x , y - 1)) {
solver(x, y - 1, cnt + 1, cp);
}
if(go(x, y + 1)) {
solver(x, y + 1, cnt + 1, cp);
}
}
visit[x][y] = 0;
}
// 마지막 테트로미노(DFS로 나오지 않는 케이스)
void solver2(int x, int y) {
int point;
if(go(x , y - 1) && go(x + 1, y) && go(x, y + 1)) {
point = table[x][y] + table[x][y - 1] + table[x + 1][y] + table[x][y + 1];
if(point > answer)
answer = point;
}
if(go(x - 1, y) && go(x , y - 1) && go(x + 1, y)) {
point = table[x][y] + table[x - 1][y] + table[x][y - 1] + table[x + 1][y];
if(point > answer)
answer = point;
}
if(go(x , y - 1) && go(x - 1, y) && go(x, y + 1)) {
point = table[x][y] + table[x][y - 1] + table[x - 1][y] + table[x][y + 1];
if(point > answer)
answer = point;
}
if(go(x - 1, y) && go(x , y + 1) && go(x + 1, y)) {
point = table[x][y] + table[x - 1][y] + table[x][y + 1] + table[x + 1][y];
if(point > answer)
answer = point;
}
}
int main()
{
//scanf("%d", &T);
T = 1;
for(int tc = 0; tc < T; tc++) {
answer = 0;
scanf("%d %d", &N, &M);
table.clear();
visit.clear();
table.resize(N);
visit.resize(N);
for(i = 0; i < N; i++)
for(j = 0; j < M; j++) {
int tmp;
scanf("%d", &tmp);
table[i].push_back(tmp);
visit[i].push_back(0);
}
for(i = 0; i < N; i++) {
for(j = 0; j < M; j++) {
solver(i, j, 1, 0);
solver2(i, j);
}
}
printf("%d\n", answer);
}
return 0;
}