c++ 14500 테트로미노 (rotate , 배열 돌리기)

구글에 14500 테트로미노 문제를 검색했을 때 DFS, 백트래킹 풀이만 나오고 저와 비슷한 풀이는 발견하지 못하여서 배열을 돌려서 푼 문제 풀이를 올립니다.

 

 

저는 우선 일부로 DFS , 백트래킹으로 풀지 말아야겠다가 아닌 생각을 하지 못해서 어떻게 풀어야 할까 하다가

 

처음에는 모든 종류들을 만들어서 문제를 풀려고 하였으나 문제를 풀다가 제가 실수해서 틀릴 것 같았기 때문에 그다음으로 생각난 방법으로 회전을 생각하지 않고 대칭, 일반적인 테트로미노들만 체크를 하였고 그리고 배열을 90도씩 돌려서 체크를 하는 방법으로 문제를 풀게 되었습니다. 

 

#include <bits/stdc++.h>

using namespace std;

int n, m;

int arr[505][505];
int tmp[505][505];

int func1(int y, int x) // 일자
{
    int sum = 0;
    int ny = y;
    int nx = x + 3;
    if (nx >= m || ny >= n || nx < 0 || ny < 0)
        return 0;

    for (int i = 0; i < 4; i++)
    {
        sum += arr[y][x + i];
    }

    return sum;
}

int func2(int y, int x) // ㄴ자
{
    int sum = 0;
    int nx = x + 1;
    int ny = y + 2;
    if (nx >= m || ny >= n || nx < 0 || ny < 0)
        return 0;

    sum = arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y][x + 1];

    return sum;
}

int func3(int y, int x) // 지그재그
{
    int sum = 0;
    int nx = x + 1;
    int ny = y + 2;
    if (nx >= m || ny >= n || nx < 0 || ny < 0)
        return 0;

    sum = arr[y][x] + arr[y + 1][x] + arr[y + 1][x + 1] + arr[y + 2][x + 1];

    return sum;
}

int func4(int y, int x) // ㅗ 자
{
    int sum = 0;
    int nx = x + 2;
    int ny = y + 1;
    if (nx >= m || ny >= n || nx < 0 || ny < 0)
        return 0;

    sum = arr[y][x] + arr[y][x + 1] + arr[y + 1][x + 1] + arr[y][x + 2];

    return sum;
}

int func5(int y, int x) // 네모
{
    int sum = 0;
    int nx = x + 1;
    int ny = y + 1;
    if (nx >= m || ny >= n || nx < 0 || ny < 0)
        return 0;

    sum = arr[y][x] + arr[y][x + 1] + arr[y + 1][x] + arr[y + 1][x + 1];

    return sum;
}

int func6(int y, int x) //ㄴ 자  대칭
{
    int sum = 0;
    int nx = x - 1;
    int ny = y + 2;
    if (nx >= m || ny >= n || nx < 0 || ny < 0)
        return 0;

    sum = arr[y][x] + arr[y][x - 1] + arr[y + 1][x] + arr[y + 2][x];

    return sum;
}

int func7(int y, int x) //지그재그 대칭
{
    int sum = 0;
    int nx = x - 1;
    int ny = y + 2;
    if (nx >= m || ny >= n || nx < 0 || ny < 0)
        return 0;

    sum = arr[y][x] + arr[y + 1][x] + arr[y + 1][x - 1] + arr[y + 2][x - 1];

    return sum;
}

void rotate()
{
    swap(n, m);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            tmp[i][j] = arr[m - j - 1][i];
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            arr[i][j] = tmp[i][j];
        }
    }
    return;
}

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

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
        }
    }

    int ans = 0;

    for (int k = 0; k < 4; k++)
    {
        if (k != 0)
        {

            rotate();
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int tmp = 0;
                tmp = max(tmp, func1(i, j));
                tmp = max(tmp, func2(i, j));
                tmp = max(tmp, func3(i, j));
                tmp = max(tmp, func4(i, j));
                tmp = max(tmp, func5(i, j));
                tmp = max(tmp, func6(i, j));
                tmp = max(tmp, func7(i, j));

                ans = max(ans, tmp);
            }
        }
    }

    cout << ans;
}