[Algorithm] 14500: 테트로미노

• toc {:toc}

📦14500: 테트로미노

---

[알고리즘 풀이] 강동규 Reviewed by Kade Kang (devkade12@gmail.com) Reviewed:: 2024-02-06 문제 확인하기

풀이

• 테트로미노가 대칭, 회전하여 나올 수 있는 케이스를 나누어 적용시켰다.
• 총 19가지 방식으로, 기준점에서 이동하는 픽셀 변화량을 blocks에 저장했다.
• 이후, 반복문으로 모든 픽셀을 돌면서 19개의 경우를 확인한다.
• 이때, board를 넘어서는 경우는 체크하지 않고 넘어간다.

#include <iostream>
#define endl '\n'
#define X first
#define Y second
using namespace std;
 
int n, m, board[505][505] = {};
int blocks[19][4][2] = {
    { {0, 0}, {0, 1}, {0, 2}, {0, 3}} , 
    { {0, 0}, {1, 0}, {2, 0}, {3, 0}} , 
    { {0, 0}, {1, 0}, {0, 1}, {1, 1}} , 
    { {0, 0}, {1, 0}, {2, 0}, {2, 1} },
    { {0, 0}, {0, 1}, {0, 2}, {-1, 2} },
    { {0, 0}, {0, 1}, {1, 1}, {2, 1} },
    { {0, 0}, {1, 0}, {0, 1}, {0, 2} },
    { {0, 0}, {1, 0}, {2, 0}, {2, -1} },
    { {0, 0}, {1, 0}, {1, 1}, {1, 2} },
    { {0, 0}, {0, 1}, {1, 0}, {2, 0} },
    { {0, 0}, {0, 1}, {0, 2}, {1, 2} },
    { {0, 0}, {1, 0}, {1, 1}, {2, 1} },
    { {0, 0}, {0, 1}, {-1, 1}, {-1, 2} },
    { {0, 0}, {1, 0}, {1, -1}, {2, -1} },
    { {0, 0}, {0, 1}, {1, 1}, {1, 2} },
    { {0, 0}, {0, 1}, {1, 1}, {0, 2} },
    { {0, 0}, {0, 1}, {-1, 1}, {1, 1} },
    { {0, 0}, {1, 0}, {1, -1}, {1, 1} },
    { {0, 0}, {1, 0}, {1, 1}, {2, 0} },
};
 
void Input(){
    cin >> n >> m;
    for(int row = 0; row < n; row++){
        for(int col = 0; col < m; col++){
            cin >> board[row][col];
        }
    }
}
 
bool is_inside(int row, int col){
    if (row < 0 || row >= n || col < 0 || col >= m) return false;
    return true;
}
 
int tetromino(){
    int max = 0;
    
    for(int row = 0; row < n; row++){
        for(int col = 0; col < m; col++){
            int temp = 0;
            for(int i = 0; i < 19; i++){
                if (!is_inside(row+blocks[i][2][0], col+blocks[i][2][1]) || !is_inside(row+blocks[i][3][0], col+blocks[i][3][1])) continue;
                temp = board[row+blocks[i][0][0]][col+blocks[i][0][1]] + board[row+blocks[i][1][0]][col+blocks[i][1][1]] + \
                        board[row+blocks[i][2][0]][col+blocks[i][2][1]] + board[row+blocks[i][3][0]][col+blocks[i][3][1]];
                if (temp > max) max = temp;
            }
        }
    }
    return max;
}
 
void Solution(){
    int max;
    max = tetromino();
    cout << max << endl;
}
 
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}