[BOJ 14500] 테트로미노

접근 방식 : 어떻게 접근해야 할지 몰라서 http://suriisurii.tistory.com/26 surisuri 님 풀이 방법을 참고해 풀었다. ㅗ ㅓ ㅏ ㅜ 도형을 제외한 모든 도형이 dfs로 접근 가능하다는 사실을 깨닫지 못해서 힘들었던 것 같다. ㅗ ㅓ ㅏ ㅜ 도형을 따로 만들어 둔 뒤에 완전 탐색을 돌리면서 최댓값을 뽑아냈다.

#include <iostream>
#include <cstring>
using namespace std;
int N, M;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int ddx[4][4] = { { -1,1,0 },{ 0,1,0 },{ 0,-1,1 },{ 0,-1,0 } };
int ddy[4][4] = { { 0,0,1 },{ -1,0,1 },{ -1,0,0 } ,{-1,0,1 } };
int map[501][501];
int value[501][501];
int visit[501][501];
int ans = 0;
 
void dfs(int x, int y, int total, int cnt) {
    if (cnt == 4) {
        //계산
        if (ans < total) { ans = total; }
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (visit[nx][ny] == 1 || nx < 1 || nx > N || ny < 1 || ny > M) { continue; }
        visit[nx][ny] = 1;
        dfs(nx, ny, total + value[nx][ny], cnt + 1);
        visit[nx][ny] = 0;
    }
}
 
void onePiece(int x, int y, int total) {
 
    for (int i = 0; i < 4; i++) {
        int sum = total;
        for (int j = 0; j < 4; j++) {
 
            int nx = x + ddx[i][j];
            int ny = y + ddy[i][j];
 
            if (visit[nx][ny] == 1 || nx < 1 || nx > N || ny <1 || ny > M) { continue; }
            sum += value[nx][ny];
        }
        if (ans < sum) { ans = sum; }
    }
    return;
}
int main() {
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> value[i][j];
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            visit[i][j] = 1;
            dfs(i, j, value[i][j], 1);
            onePiece(i, j, value[i][j]);
            visit[i][j] = 0;
        }
    }
    cout << ans << endl;
    return 0;
}