[Baekjoon,14500]테트로미노

해결

초기에는 모든 도형을 상수 배열에 저장시켜서 반복문을 돌려야 하는 줄 알았다. 그러나 방법은 있었다.

한 붓 그리기

위 그림에서 한 붓으로 그릴 수 있는 도형은 ‘ㅜ’ 모양을 제외한 도형이다. 즉, 백트래킹을 통해 여러 방향으로 탐색을 하는 중 길이가 4가 되었을 경우 최고 값을 갱신 시키면 된다. 이때 이전에 움직인 방향과 반대가 되는 방향으로 이동하면 방문한 곳을 다시 방문하니 이 부분은 제외해야 한다.

남은 도형인 ‘ㅜ’ 모양은 따로 상수 배열을 만들어 따로 합을 구해 최고 값 갱신 여부를 확인하고 갱신하면 된다.

최적화 하기

더 나아가 최적화를 할 수 있는데, 방법은 가지치기이다.
백트래킹 도중 도형을 완성시켜 봤자 이미 구한 최대 값보다 커질 수 없는 경우 곧 바로 탐색을 종료하는 것이다. 이는 맵에서 가장 큰 원소를 찾아서 계산하면 구현할 수 있다.

구현

실제 구현시 입력 값이 많아 입력 속도가 느린 cin 대신 scanf를 사용했다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

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

// 'ㅗ' 모양의 방향 별 위치
const int ex[4][4]={ {0,-1,0,1},{0,0,1,0},{0,-1,1,0},{0,-1,0,0} };
const int ey[4][4]={ {0,0,-1,0},{0,-1,0,1},{0,0,0,1},{0,0,-1,1} };

int map[MAX][MAX];
int H,W;
int ret,maxNum;

inline bool inRange(const int y, const int x)
{
    return 0<=y && y<H && 0<=x && x<W;
}

// len 길이이고 dir방향으로 움직였고 합이 sum이며 현재 위치가 (y,x)
void dfs(int y, int x, int dir, int sum, int len)
{
    if(len==4)
    {
        ret=max(ret,sum);
        return;
    }
    // 가지치기: 아무리 더해도 현재 얻은 최고 값을 넘길 수 없음
    if(ret>(4-len)*maxNum+sum)
        return;
    for(int i=0;i<4;++i)
        // 이전 방향과 반대 방향은 제외 한다.
        if(abs(dir-i)!=2)
        {
            int ny=y+dy[i];
            int nx=x+dx[i];
            // 종이를 벗어나면 안된다.
            if(!inRange(ny,nx))
                continue;
            dfs(ny,nx,i,sum+map[ny][nx],len+1);
        }
}

// 'ㅗ' 모양을 만들어 합을 구한다.
void calcException(int y, int x)
{
    // 가지치기
    if(ret>3*maxNum+map[y][x])
        return;
    for(int i=0;i<4;++i)
    {
        bool canMake=true;
        int sum=0;
        for(int pos=0;pos<4;++pos)
        {
            int ny=y+ey[i][pos];
            int nx=x+ex[i][pos];
            if(!inRange(ny,nx))
            {
                canMake=false;
                break;
            }
            sum+=map[ny][nx];
        }
        // 조각을 만들 수 있을 경우 
        if(canMake)
            ret=max(ret,sum);
    }
}

int main()
{
    cin>>H>>W;
    maxNum=0;
    for(int y=0;y<H;++y)
        for(int x=0;x<W;++x)
        {
            scanf("%d",&map[y][x]);
            maxNum=max(maxNum,map[y][x]);
        }
    
    // 모든 위치에서 시작해보며 도형을 배치한다.
    for(int y=0;y<H;++y)
        for(int x=0;x<W;++x)
        {
            dfs(y,x,-1,map[y][x],1);
            // 'ㅗ' 조각은 따로 처리한다.
            calcException(y,x);
        }
    
    cout<<ret<<endl;
    return 0;
}