테트로미노 백준 14500번

문제

테트로미노 백준 14500번

리뷰

완전 탐색으로 풀었다.

5종류의 테트로미노가 주어진다. 얘네를 대칭, 회전시킬 수 있다.

한 칸마다 숫자가 쓰여진 크기가 NxM인 종이가 있다.

이 종이에 테트로미노 '하나'를 놓을 때, 테트로미노가 놓인 칸에 쓰여있는 수들의 최댓값을 구하면 된다.

도형을 놓는 경우의 수

1x4 모양 도형은 세로/가로 이렇게 2가지 경우가 있다. 2x2 모양 도형은 1가지 경우 뿐이다.

나머지 3가지 도형은 회전/대칭 시켜보면 16가지가 나온다.

그래서 도형을 놓는 모양의 경우의 수는 총 19가지다.

1x4 , 4x1, 2x2 를 제외하고서는 나머지 도형들이 인덱스 처리하기가 까다로워서 자꾸 틀렸다.

그래서 2x3 크기의 6칸의 합을 더해놓고, 6칸 중에 2칸의 숫자를 빼는 것으로 코드를 바꿨다.

예를 들어, 아래처럼 세로 2 가로 3, 의 네모칸이 있으면 숫자 총합을 구해둔다.

[ O ] [ O ] [ O ]

[ O ] [ O ] [ O ]

6칸 총합에서 윗줄에서 첫번째, 세번째 숫자 자리의 값를 빼면 ' ㅗ ' 모양 도형의 합을 구한것과 같다.

[ X ] [ O ] [ X ]

[ O ] [ O ] [ O ]

다른 위치를 빼면 'ㄴ' 모양 도형이 합을 구한것과 같게 된다.

[ O ] [ X ] [ X ]

[ O ] [ O ] [ O ]

---

다 풀고 나니깐 DFS로 푸신 분 코드가 있었다.

코드

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

// 테트로미노  (BOJ 14500) 

int N, M;
int B[501][501]; 
int ans;
int i, j, a, b;

int main(void){

    cin >> N >> M; // 세로, 가로  

    int sum=0;


    // 입력받기
    for(i=1; i <= N; i++){ // 행 (세로)

        for(j=1; j <= M; j++){ // 열 (가로)
             cin >> B[i][j];
        } 
    }


    for(i=1; i <= N; i++){ // 행 (세로) 

        for(j=1; j <= M; j++){ // 열 (가로) 

            if(j+3 <= M){ //   1x4 
                sum = B[i][j] + B[i][j+1] + B[i][j+2] + B[i][j+3];
                ans = max(ans, sum);
            }

            if(i+3 <= N){ //   4x1
                sum = B[i][j] + B[i+1][j] + B[i+2][j] + B[i+3][j];
                ans = max(ans, sum);
            }

            if(j+1 <= M && i+1 <= N){ // 2x2 네모  
                sum = B[i][j] + B[i+1][j] + B[i][j+1] + B[i+1][j+1];
                ans = max(ans, sum);
            }


            // 세로2 가로3 내부에서 
            if(i+1 <= N && j+2 <= M){

                int six_sum = 0;

                for(a=i; a <= (i+1); a++){
                    for(b=j; b <= (j+2); b++){
                        six_sum += B[a][b];
                    }
                }

                sum = six_sum - (B[i+1][j] + B[i+1][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i+1][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j] + B[i][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j+1] + B[i][j+2]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j] + B[i+1][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j+1] + B[i+1][j+2]);
                ans = max(ans, sum);
            } 

            // 세로3 가로2 내부에서 
            if(i+2 <= N && j+1 <= M){

                int six_sum = 0;

                for(a=i; a <= (i+2); a++){
                    for(b=j; b <= (j+1); b++){
                        six_sum += B[a][b];
                    }
                }

                sum = six_sum - (B[i][j+1] + B[i+1][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i+1][j]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j] + B[i+2][j]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+1][j+1] + B[i+2][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j+1] + B[i+2][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i+2][j]);
                ans = max(ans, sum);

                sum = six_sum - (B[i][j] + B[i+2][j+1]);
                ans = max(ans, sum);

                sum = six_sum - (B[i+2][j] + B[i][j+1]);
                ans = max(ans, sum);
            }     
        }
    }

    cout << ans;

    return 0;

}