[BOJ] 14500번 테트로미노 (C++)

14500번: 테트로미노 (acmicpc.net)

14500번: 테트로미노

- 접근

첫 접근에서는 브루트포스말고 다른 방법으로 풀 수 있을까 고민을 했지만 없을 것 같다는 결론을 냈다.

모든 테트로미노의 좌상단 블록을 시작점으로 잡고 인덱스 변경값을 배열에 넣어 관리했다.

이후, 범위 초과와 대칭 및 회전 케이스를 고려하여 탐색을 하도록 구현했다.

- 풀이

신경쓸 부분은 위에서 언급한 2가지 (1) 범위초과, (2) 대칭 및 회전 케이스이다.

 

1. 범위초과

다른 맵 탐색 문제에서 사용한 최소 및 최대 범위를 체크하는 방식으로 구현했다.

 

2. 대칭 및 회전 케이스

대칭과 회전 케이스는 각각 2가지, 4가지의 경우의 수가 있다. 그러므로 한 테트로미노가 8(2*4)가지의 탐색 케이스를 가진다.

대칭은 x 인덱스에 -1을 곱해 y축 대칭시켰다.
회전은 x 인덱스는 y 인덱스로, y 인덱스는 x에 -1을 곱해 시계 방향으로 회전시켰다.

 

이후, 모든 경우를 탐색해 최대 크기의 범위를 찾는다.

- 코드

#include <iostream>
#include <vector>
#include <utility>
#define MAX 500
#define TETRO_NUM 5
#define TETRO_LEN 3
#define SYM 2
#define TURN 4
#define ANTI 1
using namespace std;

int N, M;
int arr[MAX][MAX];
int maxNum = 0;
vector<pair<int, int> > tetrominos[TETRO_NUM];

void setTetromino()
{
    tetrominos[0].push_back(make_pair(1, 0));
    tetrominos[0].push_back(make_pair(2, 0));
    tetrominos[0].push_back(make_pair(3, 0));

    tetrominos[1].push_back(make_pair(1, 0));
    tetrominos[1].push_back(make_pair(0, 1));
    tetrominos[1].push_back(make_pair(1, 1));

    tetrominos[2].push_back(make_pair(0, 1));
    tetrominos[2].push_back(make_pair(0, 2));
    tetrominos[2].push_back(make_pair(1, 2));

    tetrominos[3].push_back(make_pair(0, 1));
    tetrominos[3].push_back(make_pair(1, 1));
    tetrominos[3].push_back(make_pair(1, 2));

    tetrominos[4].push_back(make_pair(1, 0));
    tetrominos[4].push_back(make_pair(2, 0));
    tetrominos[4].push_back(make_pair(1, 1));
}

int getSumOfZone(int i, int j, vector<pair<int,int>> tetro, int turn, int sym) 
{
    int s = (sym == ANTI) ? 1 : -1;

    for (; turn < TURN; turn++)
        for (int k = 0; k < TETRO_LEN; k++) {
            int x = tetro[k].first;
            int y = tetro[k].second;
            tetro[k] = make_pair(y, x * -1);
        }

    int sum = arr[i][j];

    for(int k = 0; k < TETRO_LEN; k++) {
        int nx = j + (tetro[k].first * s);
        int ny = i + tetro[k].second;

        if (nx < 0 || ny < 0 || N <= ny || M <= nx)
            return 0;

        sum += arr[ny][nx];
    }

    return sum;
}

void searchAllCase(int i, int j, int k)
{
    for (int sym = 0; sym < SYM; sym++)
        for (int turn = 0; turn < TURN; turn++)
            maxNum = max(maxNum, getSumOfZone(i, j, tetrominos[k], turn, sym));
}

void solve() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            for (int k = 0; k < TETRO_NUM; k++)
                searchAllCase(i, j, k);
}

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> N >> M;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> arr[i][j];

    setTetromino();
    solve();

    cout << maxNum << '\n';
    return 0;
}

---

메모리와 시간을 더 줄일 수 있는 방법은 무조건 있는 코드...!