기본 개념
https://www.acmicpc.net/problem/14500
이번에는 테트리스 문제이다. 테트리스 문제는 다른 문제보다 세팅이 조금 오래 걸렸던 것 같다. 테트리스 블록, 즉 테트리미노 모양을 구현해주어야 했기 때문이다. 테트리미노 모양은 총 7개 존재하고, 각각 4가지 회전된 방향이 존재한다. 각 회전 모양별로 총 4개의 칸을 차지하게 되고, 각 칸은 또 2D 좌표로 이루어져 있다.
int tetrimino[7][4][4][2];위와 같은 변수를 만들어 준 후, 이제 하나하나 입력을 해줄 것이다. 입력하는 것이 귀찮기는 하지만 프로그램의 속도는 매우 빠르게 해준다. 테트리미노의 회전을 그때그때 계산해서 작업하면 계산 시간이 너무 오래 걸리게 되기 때문이다. 안그래도 다양한 가능성을 다 확인해야하는 문제인데, 회전 계산이 많이 들어가면 너무 무거워진다.
본 문제는 테트리미노를 어떻게 배치했을때 가장 많은 숫자를 얻을수 있는지를 구하는 문제로, 사실상 모든 경우의 수를 다 확인해야만 하는 문제이다. 다중 루프를 활용하여 모든 좌표, 모든 테트리미노 모양을 모든 회전으로 배치했을때의 점수들의 최댓값을 산출해주면 되는 간단한 문제이다.
구현
테트리미노 정의
#define empty {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}
short tetrimino[7][4][4][2] = {
{ // I-block
{ {0, 0}, {0, 1}, {0, 2}, {0, 3} },
{ {0, 0}, {1, 0}, {2, 0}, {3, 0} },
{empty},
{empty}
},
{ // o-block
{ {0, 0}, {1, 0}, {1, 1}, {0, 1} },
{empty},
{empty},
{empty}
},
{ // z-block
{ {1, 0}, {1, 1}, {0, 1}, {0, 2} },
{ {0, 0}, {1, 0}, {1, 1}, {2, 1} },
{empty},
{empty}
},
{ // s-block
{ {0, 1}, {1, 1}, {1, 0}, {2, 0} },
{ {0, 0}, {0, 1}, {1, 1}, {1, 2} },
{empty},
{empty}
},
{ // t-block
{ {0, 0}, {1, 0}, {2, 0}, {1, 1} },
{ {1, 0}, {1, 1}, {1, 2}, {0, 1} },
{ {1, 0}, {0, 1}, {1, 1}, {2, 1} },
{ {0, 0}, {0, 1}, {0, 2}, {1, 1} }
},
{ // L-block
{ {0, 0}, {0, 1}, {0, 2}, {1, 2} },
{ {0, 0}, {1, 0}, {2, 0}, {0, 1} },
{ {0, 0}, {1, 0}, {1, 1}, {1, 2} },
{ {0, 1}, {1, 1}, {2, 1}, {2, 0} }
},
{ // J-block
{ {1, 0}, {1, 1}, {1, 2}, {0, 2} },
{ {0, 0}, {0, 1}, {1, 1}, {2, 1} },
{ {0, 0}, {0, 1}, {0, 2}, {1, 0} },
{ {0, 0}, {1, 0}, {2, 0}, {2, 1} }
}
};우선, precompiler 매크로로 empty라는것을 만들어두었다. 해당 회전 모양은 기존 모양과 같은 모양이라 참고하지 않아도 된다는 의미로 생각하면 될것 같다. 예를 들어, ㅁ모양 블록의 경우, 아무리 회전을 해도 같은 모양이기 때문에 empty가 세개나 존재하게 된다.
입력
int n, m;
int map[500][500];
cin >> n >> m;
for(int y = 0 ; y < n ; y++) {
for(int x = 0 ; x < m ; x++) {
cin >> map[x][y];
}
}맵 입력은 기존과 다른것이 없기 때문에 크게 설명할 것이 없다. n, m값을 받아서 차례로 입력을 받아준다.
탐색 시작
int max = 0;
for(int y = 0 ; y < n ; y++) {
for(int x = 0 ; x < m ; x++) { // for each coord
...우선 각 좌표별로 루프를 돌려줄 것이다. n이 세로, m이 가로 크기의 입력이였기 때문에 각 좌표를 탐색하게 된다.
int max = 0;
for(int y = 0 ; y < n ; y++) {
for(int x = 0 ; x < m ; x++) { // for each coord
for(int i = 0 ; i < 7 ; i++) { // for each tetrimino
for(int rot = 0 ; rot < 4 ; rot++) { // for each rotation
if(tetrimino[i][rot][0][0] == -1) continue;
...루프를 두개 더 추가하여 테트리미노 종류별, 회전별로 체크하는 루프를 만들었다. 테트리미노 종류는 7, 회전 종류는 4개이기 때문에 위와 같이 표현하면 된다.
단, 만약 현재 테트리미노 값에 <code<-1</code>이 존재할 경우, 위에 정의한것처럼 해당 회전은 탐색할 이유가 없는 것이므로 다음으로 넘겨준다. 여기서 continue가 아닌 break를 쓴 이유는, empty 값은 항상 회전 배열의 뒤쪽에 존재하게 해뒀기 때문이다. 그 뒤로는 더이상 확인할 이유가 없기 때문에 다음 회전이 아닌 다음 테트리미노로 넘어가면 된다.
int max = 0;
for(int y = 0 ; y < n ; y++) {
for(int x = 0 ; x < m ; x++) { // for each coord
for(int i = 0 ; i < 7 ; i++) { // for each tetrimino
for(int rot = 0 ; rot < 4 ; rot++) { // for each rotation
if(tetrimino[i][rot][0][0] == -1) break;
// calculate sum
int sum = 0;
for(int k = 0 ; sum != -1 && k < 4 ; k++) {
if(!is_validpos(n, m, x + tetrimino[i][rot][k][0], y + tetrimino[i][rot][k][1])) {
sum = -1;
} else sum += map[x + tetrimino[i][rot][k][0]][y + tetrimino[i][rot][k][1]];
}
if(sum > max) {
max = sum;
}이제 계산을 해주면 된다. 테트리미노의 각 좌표 4개에 대하여 이전 포스트에서부터 계속 사용해온 is_validpos 함수로 해당 좌표가 사용 가능한지부터 체크해준다. 만약 사용 불가능이라면 sum을 -1로 해주어 루프를 끝내주면 된다. 만약 사용 가능하다면 sum에 현재 맵 좌표의 수치를 더해주면 된다.
4개 좌표를 각각 확인하였다면 이제 현재 테트리미노 배치의 값이 max값보다 큰지를 확인하여 저장해주면 된다.
모든 루프가 끝난 후, max를 출력해주면 된다.
마무리
| 메모리 | 시간 |
|---|---|
| 2876KB | 88ms |
비교적 출력 시간이 조금 걸리는 문제일수밖에 없는 환경이다. 경우의 수가 너무 많고, 하나하나 체크해주어야 하기 때문이다. 계산수를 줄이기 위하여 테트리미노의 회전을 preprocess하여 미리 입력해두었지만, 그래도 오래 걸리는 것은 어쩔 수 없는 것 같다.
Comments