[구현]백준14500번 테트로미노

백준14500

문제를 풀고 검색해보니 dfs로 푸는 방법도 있었다.

이 모양을 제외하고 나머지 모양들로 구할 수 있는 모든 조합은, 한 지점에서 깊이 4로 가능한 모든 dfs를 해본 것과 같았다. 따라서 맵의 한 지점에서 깊이 4의 dfs를 모두 수행하고, (상,하,좌,우) 위의 저 모양만 따로 처리를 해주는 풀이 방법이 있었다.

다만 나는 그 방법을 생각해내지 못했고, 다음과 같은 방법을 사용했다.

각 모양에 대해 회전과 대칭을 하는 경우를 배열로 정리하는 것을 시도했다.

각 블록들을 배열로 나타내면 다음과 같다.

해당 블록들을 대칭 시키는 경우는 다음과 같다.

대칭시키는 경우는 총 4 가지이다. (원래 자리 포함)

(1,1) 은 원래 그대로, (1,-1) 은 y 축에 대한 대칭, (-1,1)은 x 축에 대한 대칭, (-1,-,1)은 y축에 대한 대칭의 x 축에 대한 대칭이다.

블록이 회전하는 경우의 수는 두 가지이다. 이 경우는 y와 x 를 뒤바꾸면 만들어볼 수 있다.

따라서, 대칭하는 경우의 수를 모두 확인한 뒤, 회전시켜 다시 대칭의 경우의 수를 모두 확인하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N,M;
int arr[500][500];
int piece1_y[4] = {0,1,2,3};
int piece1_x[4] = {0,0,0,0};

int piece2_y[4] = {0,0,1,1};
int piece2_x[4] = {0,1,0,1};

int piece3_y[4] = {0,1,2,2};
int piece3_x[4] = {0,0,0,1};

int piece4_y[4] = {0,1,1,2};
int piece4_x[4] = {0,0,1,1};

int piece5_y[4] = {0,0,1,0};
int piece5_x[4] = {0,1,1,2};

int mk_y[] = {1,1,-1,-1};
int mk_x[] = {1,-1,1,-1};

int answer;

void check(int y,int x){
    int maxSum = 0;
    for(int i=0;i<4;i++){
        int tmp1 = 0;
        int tmp2 = 0;
        int tmp3 = 0;
        int tmp4 = 0;
        int tmp5 = 0;
        vector<int> sums;
        for(int j=0;j<4;j++){
            int y_1 = y + piece1_y[j] * mk_y[i];
            int x_1 = x + piece1_x[j] * mk_x[i];
            if(y_1 >=0 && x_1 >=0 && y_1 < N && x_1 < M) tmp1 += arr[y_1][x_1];
            int y_2 = y + piece2_y[j] * mk_y[i];
            int x_2 = x + piece2_x[j] * mk_x[i];
            if(y_2 >=0 && x_2 >=0 && y_2 < N && x_2 < M) tmp2 += arr[y_2][x_2];
            int y_3 = y + piece3_y[j] * mk_y[i];
            int x_3 = x + piece3_x[j] * mk_x[i];
            if(y_3 >=0 && x_3 >=0 && y_3< N && x_3 < M) tmp3 += arr[y_3][x_3];
            int y_4 = y + piece4_y[j] * mk_y[i];
            int x_4 = x + piece4_x[j] * mk_x[i];
            if(y_4 >=0 && x_4 >=0 && y_4< N && x_4 < M) tmp4 += arr[y_4][x_4];
            int y_5 = y + piece5_y[j] * mk_y[i];
            int x_5 = x + piece5_x[j] * mk_x[i];
            if(y_5 >=0 && x_5 >=0 && y_5< N && x_5 < M) tmp5 += arr[y_5][x_5];
        }
        sums.push_back(tmp1);
        sums.push_back(tmp2);
        sums.push_back(tmp3);
        sums.push_back(tmp4);
        sums.push_back(tmp5);
        sort(sums.begin(),sums.end());
        if(sums[4] >= maxSum) maxSum = sums[4];
    }
    for(int i=0;i<4;i++){
        int tmp1 = 0;
        int tmp2 = 0;
        int tmp3 = 0;
        int tmp4 = 0;
        int tmp5 = 0;
        vector<int> sums;
        for(int j=0;j<4;j++){
            int y_1 = y + piece1_x[j] * mk_x[i];
            int x_1 = x + piece1_y[j] * mk_y[i];
            if(y_1 >=0 && x_1 >=0 && y_1< N && x_1 < M) tmp1 += arr[y_1][x_1];
            int y_2 = y + piece2_x[j] * mk_x[i];
            int x_2 = x + piece2_y[j] * mk_y[i];
            if(y_2 >=0 && x_2 >=0 && y_2< N && x_2 < M) tmp2 += arr[y_2][x_2];
            int y_3 = y + piece3_x[j] * mk_x[i];
            int x_3 = x + piece3_y[j] * mk_y[i];
            if(y_3 >=0 && x_3 >=0 && y_3< N && x_3 < M) tmp3 += arr[y_3][x_3];
            int y_4 = y + piece4_x[j] * mk_x[i];
            int x_4 = x + piece4_y[j] * mk_y[i];
            if(y_4 >=0 && x_4 >=0 && y_4< N && x_4 < M) tmp4 += arr[y_4][x_4];
            int y_5 = y + piece5_x[j] * mk_x[i];
            int x_5 = x + piece5_y[j] * mk_y[i];
            if(y_5 >=0 && x_5 >=0 && y_5< N && x_5 < M) tmp5 += arr[y_5][x_5];
        }
        sums.push_back(tmp1);
        sums.push_back(tmp2);
        sums.push_back(tmp3);
        sums.push_back(tmp4);
        sums.push_back(tmp5);
        sort(sums.begin(),sums.end());
        if(sums[4] >= maxSum) maxSum = sums[4];
    }
    if(maxSum >= answer){
        answer = maxSum;
    }
    
}

int main(){
    cin >> N >> M;

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin >> arr[i][j];
        }
    }
    answer = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            check(i,j);
        }
    }
    cout << answer;
}