[코드트리 챌린지] 트로미노

[실력진단 테스트]

[문제]

https://www.codetree.ai/cote/13/problems/tromino?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제 풀이]

백준 테트로미노와 비슷한 문제이다.

처음 보면 1. 이차원 배열을 모두 방문할 것. 2. 해당 배열에서 테트리스의 위치의 숫자들의 합을 구할 것. 3. 블록은 돌아갈 수 있으니 4번 돌릴것 의 3단계로 구현이 되어야 한다고 생각할 수 있다.

하지만 일반적으로 여기서 3번의 경우에서 발목이 잡히기 쉬운데

블록을 돌리는 작업이 생각보다 수고롭다는 것을 실제로 구현을 해보면 알 수가 있다.

 

그러니 여기선 블록을 직접 돌리지 말고 사람이 돌려준 뒤에 해당 위치를 모두 배열로 만들어서 알려주도록 하자.

 

 

이와 같은 총 6가지의 경우가 블록을 돌렸을 때 나올 수 있는 경우이니 이를 벡터에 넣어주도록 하자.

//테트리스 => [6][3][2]
vector<vector<vector<int> > > tetris = {
    {{0,0},{1,0},{1,1}},
    {{0,0},{0,1},{1,1}},
    {{0,1},{1,0},{1,1}},
    {{0,0},{0,1},{1,0}},
    {{0,0},{0,1},{0,2}},
    {{0,0},{1,0},{2,0}}
};

 

그러면 위와 같은 3차원 배열이 나올 것이고 우리들은 이를 통해서 해당 문제를 보다 쉽게 접근을 할 수가 있다.

 

처음 말했던 1,2,3 구현에서 3의 구현이 완료가 되었으니 1을 구현해보면

for(int i = 0;i<n;i++){
    for(int j = 0;j<m;j++){
        //테트리스 종류.
        for(int k = 0;k<6;k++){
        	answer = max(answer, 테트리스 합을 구하는 함수);
        }
    }
}

 

이와 같이 구현이 되고 그러면 이제 테트리스의 합을 구하는 구현에 넘어가보도록 하자.

 

테트리스 합을 구하는 함수 또한 생각보다 어렵지 않은데

int maxCheck(int x, int y, int k){
    int score = 0;
    for(int i = 0;i<3;i++){
        int nextX = x + tetris[k][i][0];
        int nextY = y + tetris[k][i][1];
        //inRange 함수는 해당 숫자가 범위 안인지 확인하는 함수
        if(inRange(nextX,nextY) == false) {
            return -1;
        }
        score += boards[nextX][nextY];
    }
    return score;
}

 

bfs에서 for문을 이용했던것과 비슷하게 쉽게 구현이 가능하다.

주의해야 할 점은 inRange(nextX,nextY) == true일때만 더하게 만들면

 

이와 같은 경우에서 6 과 9를 더한 값을 구한채로 반환을 해줄 수 있다.

해당 문제에서는 모든 값이 양수이니 문제가 되지 않지만 만약 해당 문제에 음수가 섞인다면 이와 같은 경우로 오답이 나올 수 있으니 범위를 벗어나면 바로 반환을 해주도록 하자.

[회고]

처음에 블록 회전에서 어떻게 해야 될지를 몰라서 어려워 했는데 발상을 해보면 어렵지 않게 풀릴 수 있는 문제였다.

또한, 해당 문제에서는 블록 회전이 필요 없지만 블록 회전을 실제로 사용하는 문제도 있으니 연습해 주도록 하자.

[코드]

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

using namespace std;

int n,m;
int boards[210][210];

//tetris가 할 수 있는 모든 경우.
//테트리스 => [6][3][2]
vector<vector<vector<int> > > tetris = {
    {{0,0},{1,0},{1,1}},
    {{0,0},{0,1},{1,1}},
    {{0,1},{1,0},{1,1}},
    {{0,0},{0,1},{1,0}},
    {{0,0},{0,1},{0,2}},
    {{0,0},{1,0},{2,0}}
};

bool inRange(int x, int y){
    if(x >= 0 && x < n && y >= 0 && y < m){
        return true;
    }
    return false;
}

int maxCheck(int x, int y, int k){
    int score = 0;
    for(int i = 0;i<3;i++){
        int nextX = x + tetris[k][i][0];
        int nextY = y + tetris[k][i][1];
        if(inRange(nextX,nextY) == false) {
            return -1;
        }
        score += boards[nextX][nextY];
    }
    return score;
}

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

    int answer = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            //테트리스 종류.
            for(int k = 0;k<6;k++){
                answer = max(answer, maxCheck(i,j,k));
            }
        }
    }
    cout<<answer<<endl;
    return 0;
}