[Baekjoon][14500] 테트로미노

출처 - 백준사이트

14500번: 테트로미노

나의 풀이

'ㅗ' 모양의 블럭을 제외하고 나머지 블록은 시작점에서 부터 3칸을 임의로 이동하는 경우이다.
따라서, 완전 탐색으로 이미 왔던 칸은 가지않도록하고 3칸을 이동한 후에 최대값을 구하면 된다.
'ㅗ' 모양은 따로 예외처리하여 구한다.

#include <iostream>

#define MAX_SIZE    500

using namespace std;

const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};

int N, M;
int map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
int result = 0;

void tetromino(int y, int x, int cnt, int sum) {
    if (cnt == 3) {
        if (result < sum)
            result = sum;

        return;
    }

    for (int idx = 0 ; idx < 4 ; idx++) {
        int ny = y + dy[idx];
        int nx = x + dx[idx];

        if (0 <= ny && ny < N && 0 <= nx && nx < M && !visit[ny][nx]) {
            visit[ny][nx] = true;
            tetromino(ny, nx, cnt + 1, sum + map[ny][nx]);
            visit[ny][nx] = false;
        }
    }
}

void tetromino_except(int y, int x) {
    if (y + 2 < N) {
        int temp = map[y][x] + map[y+1][x] + map[y+2][x];

        if (x - 1 >= 0) {
            if (result < temp + map[y+1][x-1])
                result = temp + map[y+1][x-1];
        }

        if (x + 1 < M) {
            if (result < temp + map[y+1][x+1])
                result = temp + map[y+1][x+1];
        }
    }

    if (x + 2 < M) {
        int temp = map[y][x] + map[y][x+1] + map[y][x+2];

        if (y - 1 >= 0) {
            if (result < temp + map[y-1][x+1])
                result = temp + map[y-1][x+1];
        }

        if (y + 1 < N) {
            if (result < temp + map[y+1][x+1])
                result = temp + map[y+1][x+1];
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> N >> M;

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

    for (int y = 0 ; y < N ; y++) {
        for (int x = 0 ; x < M ; x++) {
            visit[y][x] = true;
            tetromino(y, x, 0, map[y][x]);
            visit[y][x] = false;
            tetromino_except(y, x);
        }
    }

    cout << result;
}