[백준] 14500번 테트리미노

 

[적용한 알고리즘]

브루트 포스, 재귀

 

[아이디어]

1. 한칸만 정하고 인접한 3칸만 이동하면 1가지 경우를 제외하고 전부 나타낼 수 있다.

2. 예외 케이스는 따로 처리해준다

 

[생각의 흐름 / 절차] 

1. 모양을 다해봐야하나? 너무 노가다여서 하기가 싫었다. 모양 간의 공통점을 찾고싶었다.

(ㅗ) 모양을 제외하면 나머지는 인접하게 붙은 4칸의 모양이었다. 

 

2. 경우의 수를 다 해봐야겠다. 한칸만 정하면 대부분의 경우의 수 표현가능,

나머지 한가지 (ㅗ,ㅜ,ㅓ,ㅏ) 모양은 따로 예외케이스 처리해서 빼줘야겠다.

 

3. 다음 칸으로 이동할때 dfs와는 동일하게 check 배열에 체크를 해주고,

재귀를 돌고 나올 때 check를 해제해줘야겠다.

-> 그래야 다른 점에서 시작하는 경우를 계산할 수 있으니까.

중복은 생기겠지만, 고려하지 않아도 된다. 어차피 최댓값만 구하면 되니까.

 

4. 모든 칸마다 반복문을 돌면서 실행해서 최댓값을 정해야겠다.

 

 

[교훈]

열심히 예외 케이스 처리하자. 이런 식으로 최대한 같은 걸로 묶고 예외로 빼줘야할 수도 있다. 

 

<코드>

#include <cstdio>
#include <algorithm>
#define SIZE 501
using namespace std;

int map[SIZE][SIZE];
bool check[SIZE][SIZE];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
int n, m;
int ans = 0;

void tetrimino(int cnt, int curx, int cury, int sum){
    if (cnt == 4){
        ans = max(ans, sum);
        return;
    }

    if (check[curx][cury]) return;

    check[curx][cury] = true;

    for (int k = 0; k < 4; k++){
        int nx = curx + dirx[k];
        int ny = cury + diry[k];

        if (0 <= nx && nx < n && 0 <= ny && ny < m){
            tetrimino(cnt + 1, nx, ny, sum + map[curx][cury]);
        }
    }

    check[curx][cury] = false;
}

int tetrimino2(int curx, int cury){
    int ret = -1;
    int tempSum = 0;
    //세로 방향
    if (curx + 2 < n){
        tempSum = map[curx][cury] + map[curx + 1][cury] + map[curx + 2][cury];
        if (cury + 1 < m){
            int temp = tempSum + map[curx + 1][cury + 1];
            ret = max(ret, temp);
        }
        if (cury - 1 >= 0){
            int temp = tempSum + map[curx + 1][cury - 1];
            ret = max(ret, temp);
        }
    }

    //가로 방향
    if (cury + 2 < m){
        tempSum = map[curx][cury] + map[curx][cury + 1] + map[curx][cury + 2];
        if (curx + 1 < n){
            int temp = tempSum + map[curx + 1][cury + 1];
            ret = max(ret, temp);
        }
        if (curx - 1 >= 0){
            int temp = tempSum + map[curx - 1][cury + 1];
            ret = max(ret, temp);
        }
    }

    return ret;
}

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++){
            tetrimino(0, i, j, 0);
            ans = max(ans, tetrimino2(i, j));
        }
    }

    printf("%d\n", ans);
    return 0;
}