Baekjoon. 14500. 테트로미노

14500 테트로미노

[문제 사이트 바로가기]

문제 설명

• 1×1인 정사각형을 여러 개 이어서 붙인 도형인 폴리오미노가 존재한다. 이 폴리오미노 도형들을 하나씩 숫자가 적힌 Grid에 올려 놓는다고 할 때, 폴리오미노 도형들과 겹쳐진 숫자들의 총 합중 가장 큰 값을 반환하기.
• 올려 놓는 과정에 있어서 도형들을 자유자재로 회전을 하거나 뒤집어서 사용하는 것도 가능하다.
  
  

  문제 풀이

  ---

1. 폴리오미노 도형들 모두 미리 좌표값으로 준비시켜놓는다

• 여기서 좌표값을 준비 시켜 놓을 때, (0, 0)을 기준으로 준비시켜 놓는다. 왜냐하면, 이중 포문으로 Grid에 해당하는 i, j를 돌릴 때 이 i, j를 시작 점으로 폴리오미노 도형의 좌표들을 따라서 값을 누적시켜줄 것이기 때문에.

2. 좌표값들을 회전시키거나 대칭 이동시키는 함수 추가.

• 좌표값90도 회전 코드 : (x, y) -> (y, -x)
• y축 대칭 이동 코드 : (x, y) -> (-x, y)

3. 좌표값들을 회전시키거나 대칭 이동 시키는 경우, 기준 좌표값(0,0)이 흐뜨러질 수 있으므로 반드시 (0, 0) 좌표로 이동시켜주는 로직을 포함시켜준다.

예를 들어, {{0, 0}, {0, 1}, {1, 1}, {1, 2}} 이러한 도형이 있다고 해보자. 이 좌표를 통해 그림을 그려보면,

이런 그림이 나올 것이다. 여기서 이 도형의 좌측 상단이 (0, 0)에 해당하는 좌표이다. 이 도형을 만약 90도 회전하게 된다면( (x, y) -> (y, -x)로 이동 ) 아래의 그림처럼 될 것이다.

이 도형은, 기존 도형의 좌상단을 기준으로 회전이 이루어진 것이기 때문에, (0, 0) 좌표는 이 도형의 우측 상단이 될 것이다. 이 부분에 대해서는 아래의 그림을 확인.

이 좌표를 그대로 진행하게 될 경우 grid를 기준으로는 음수에 대한 처리로 진행이 되어야 하기 때문에 도형을 기준으로 좌상단을 (0, 0)으로 맞춰주는 작업이 필요하다.

4. 풀이에 맞춰 루프 돌리기.

grid에 해당하는 이중 루프의 인덱스(i, j)를 기준으로 시작점을 잡으며, 회전 및 대칭에 대한 처리를 진행하며 테트로미노를 하나씩 배치하며 최대 값을 갱신해나간다.

정답 코드

#include
<iostream>
#include
<vector>
#include
<algorithm>

using namespace std;

int N, M;

/*

o o o o

o o x 
x o o 

o o o 
x o x 

o
o
o o

o o
o o

*/

vector<pair<int, int>> polyominoArr[5] = {

    { {0, 0}, {0, 1}, {0, 2}, {0, 3} },
    { {0, 0}, {0, 1}, {1, 1}, {1, 2} },
    { {0, 0}, {0, 1}, {0, 2}, {1, 1} },
    { {0, 0}, {1, 0}, {2, 0}, {2, 1} },
    { {0, 0}, {0, 1}, {1, 0}, {1, 1} },

};

// 0 1   x  -> y
// -1 0  y  -> -x

int answer = 0;

void Rotate90(vector<pair<int, int>>& polyomino)
{
    // (x, y) -> (y, -x)
    int minX = 500;
    int minY = 500;
    for (int i = 0; i < polyomino.size(); i++)
    {
        int x = polyomino[i].second;
        int y = polyomino[i].first;

        polyomino[i].second = y;
        polyomino[i].first = -x;

        minX = min(minX, polyomino[i].second);
        minY = min(minY, polyomino[i].first);
    }

    for (int i = 0; i < polyomino.size(); i++)
    {
        polyomino[i].first -= minY;
        polyomino[i].second -= minX;
    }
}

void FlipYAxis(vector<pair<int, int>>& polyomino)
{
    int minX = 500;
    int minY = 500;

    for (int i = 0; i < polyomino.size(); i++)
    {
        int x = polyomino[i].second;
        int y = polyomino[i].first;

        polyomino[i].second = -x;
        polyomino[i].first = y;

        minX = min(minX, polyomino[i].second);
        minY = min(minY, polyomino[i].first);
    }

    for (int i = 0; i < polyomino.size(); i++)
    {
        polyomino[i].first -= minY;
        polyomino[i].second -= minX;
    }
}

int GetSumPolyomino(vector<vector<int>>& grid, int i, int j, int type)
{
    int startY = i;
    int startX = j;

    int sum = 0;

    for (int i = 0; i < polyominoArr[type].size(); i++)
    {
        int dy = polyominoArr[type][i].first;
        int dx = polyominoArr[type][i].second;

        int nextY = startY + dy;
        int nextX = startX + dx;

        if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
            return -1;

        sum += grid[nextY][nextX];
    }

    return sum;
}

void PutPolyomino(vector<vector<int>>& grid)
{
    for (int rot = 0; rot < 4; rot++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                for (int type = 0; type < 5; type++)
                {
                    answer = max(answer, GetSumPolyomino(grid, i, j, type));
                }
            }
        }

        for (int k = 0; k < 5; k++)
        {
            Rotate90(polyominoArr[k]);
        }
    }
}

int main()
{
    cin >> N >> M;
    vector<vector<int>> grid(N, vector<int>(M));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> grid[i][j];

    PutPolyomino(grid);

    for (int k = 0; k < 5; k++)
        FlipYAxis(polyominoArr[k]);

    PutPolyomino(grid);

    cout << answer;
}