[백준] 15660 - 테트로미노(2)

테트로미노를 두개 놓고 최대값을 구하는 문제

이 문제 그냥 8개까지 놓고 생각하면 19*500*500*19*500*500의 시간이 걸린다...결론은 말도 안되는 범위

그렇기 때문에 먼저 한개를 놓았을 때 최대가 되는 걸 찾고, 그다음에 놓는 걸 생각하기로 했다

하지만 이렇게 하면, 문제가 되는게 max값이 같은것이 여러개일 경우 모두 따져 주지 못한다

그렇기 때문에 max값이 갱신될때 마다 그 위치를 구조체 배열을 선언해서 후보값들을 넣어준다

이렇게 되면 19*500*500 + 19*500*500*a까지 줄어들면서 문제를 해결할 수 있다

이렇게 해도 어마무시하게 시간이 걸릴 줄 알았는데 464ms로 생각보다 빠르게 구할 수 있었다

#include <iostream>
#define MX 502
using namespace std;
 
struct MAXCOR {
    int x, y, x1, y1, x2, y2, x3, y3;
}tmp[4], hubo[MX*MX];
 
int map[MX][MX], check[MX][MX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, M, tmpdab, dab1, dab2, cnt;
 
void dfs(int d, int x, int y, int sum, int mod)
{
    if (d == 4)
    {
        if (tmpdab < sum)
        {
            tmpdab = sum;
            if (mod)
            {
                cnt = -1;
                cnt++;
                hubo[cnt].x = tmp[0].x; hubo[cnt].y = tmp[0].y;
                hubo[cnt].x1 = tmp[1].x; hubo[cnt].y1 = tmp[1].y;
                hubo[cnt].x2 = tmp[2].x; hubo[cnt].y2 = tmp[2].y;
                hubo[cnt].x3 = tmp[3].x; hubo[cnt].y3 = tmp[3].y;
            }
        }
        if (tmpdab == sum && mod)
        {
            cnt++;
            hubo[cnt].x = tmp[0].x; hubo[cnt].y = tmp[0].y;
            hubo[cnt].x1 = tmp[1].x; hubo[cnt].y1 = tmp[1].y;
            hubo[cnt].x2 = tmp[2].x; hubo[cnt].y2 = tmp[2].y;
            hubo[cnt].x3 = tmp[3].x; hubo[cnt].y3 = tmp[3].y;
        }
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= M || ny >= N || check[ny][nx]) continue;
        check[ny][nx] = 1; tmp[d].x = nx; tmp[d].y = ny;
        dfs(d + 1, nx, ny, sum + map[ny][nx], mod);
        check[ny][nx] = 0;
    }
}
 
int main(void)
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> map[i][j];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            check[i][j] = 1; tmp[0].x = j; tmp[0].y = i;
            dfs(1, j, i, map[i][j], 1);
            int x1, x2, x3, y1, y2, y3, d1, d2, d3;
            for (int dir = 0; dir < 4; dir++)
            {
                d1 = dir; d2 = dir + 1; d3 = dir + 2;
                if (d2 > 3) d2 -= 4;
                if (d3 > 3) d3 -= 4;
                x1 = j + dx[d1]; y1 = i + dy[d1]; x2 = j + dx[d2]; y2 = i + dy[d2]; x3 = j + dx[d3]; y3 = i + dy[d3];
                tmp[1].x = x1; tmp[1].y = y1; tmp[2].x = x2; tmp[2].y = y2; tmp[3].x = x3; tmp[3].y = y3;
                if (x1 < 0 || y1 < 0 || x1 >= M || y1 >= N || x2 < 0 || y2 < 0 || x2 >= M || y2 >= N || x3 < 0 || y3 < 0 || x3 >= M || y3 >= N) continue;
                if (map[i][j] + map[y1][x1] + map[y2][x2] + map[y3][x3] > tmpdab)
                {
                    tmpdab = map[i][j] + map[y1][x1] + map[y2][x2] + map[y3][x3];
                    cnt = -1;
                    cnt++;
                    hubo[cnt].x = j; hubo[cnt].y = i;
                    hubo[cnt].x1 = x1; hubo[cnt].y1 = y1;
                    hubo[cnt].x2 = x2; hubo[cnt].y2 = y2;
                    hubo[cnt].x3 = x3; hubo[cnt].y3 = y3;
                }
                if (map[i][j] + map[y1][x1] + map[y2][x2] + map[y3][x3] == tmpdab)
                {
                    cnt++;
                    hubo[cnt].x = tmp[0].x; hubo[cnt].y = tmp[0].y;
                    hubo[cnt].x1 = tmp[1].x; hubo[cnt].y1 = tmp[1].y;
                    hubo[cnt].x2 = tmp[2].x; hubo[cnt].y2 = tmp[2].y;
                    hubo[cnt].x3 = tmp[3].x; hubo[cnt].y3 = tmp[3].y;
                }
            }
            check[i][j] = 0;
        }
    }
    dab1 += tmpdab;
    tmpdab = 0;
    for (int c = 0; c <= cnt; c++)
    {
        check[hubo[c].y][hubo[c].x] = check[hubo[c].y1][hubo[c].x1] = check[hubo[c].y2][hubo[c].x2] = check[hubo[c].y3][hubo[c].x3] = 1;
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (check[i][j]) continue;
                check[i][j] = 1; tmp[0].x = j; tmp[0].y = i;
                dfs(1, j, i, map[i][j], 0);
                int x1, x2, x3, y1, y2, y3, d1, d2, d3;
                for (int dir = 0; dir < 4; dir++)
                {
                    d1 = dir; d2 = dir + 1; d3 = dir + 2;
                    if (d2 > 3) d2 -= 4;
                    if (d3 > 3) d3 -= 4;
                    x1 = j + dx[d1]; y1 = i + dy[d1]; x2 = j + dx[d2]; y2 = i + dy[d2]; x3 = j + dx[d3]; y3 = i + dy[d3];
                    tmp[1].x = x1; tmp[1].y = y1; tmp[2].x = x2; tmp[2].y = y2; tmp[3].x = x3; tmp[3].y = y3;
                    if (x1 < 0 || y1 < 0 || x1 >= M || y1 >= N || x2 < 0 || y2 < 0 || x2 >= M || y2 >= N || x3 < 0 || y3 < 0 || x3 >= M || y3 >= N) continue;
                    if (check[y1][x1] || check[y2][x2] || check[y3][x3]) continue;
                    if (map[i][j] + map[y1][x1] + map[y2][x2] + map[y3][x3] > tmpdab)
                    {
                        tmpdab = map[i][j] + map[y1][x1] + map[y2][x2] + map[y3][x3];
                    }
                }
                check[i][j] = 0;
            }
        }
        if (dab1 + tmpdab > dab2) dab2 = dab1 + tmpdab;
        check[hubo[c].y][hubo[c].x] = check[hubo[c].y1][hubo[c].x1] = check[hubo[c].y2][hubo[c].x2] = check[hubo[c].y3][hubo[c].x3] = 0;
    }    
    cout << dab2 << endl;
    return 0;
}