[백준 14500] #129 : 테트로미노 (C++)

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

C++ 구현, 브루트포스

사진에 보이는 5개의 테트로미노를 회전, 대칭 시켜서 점수가 적혀있는 판에 놓았을 때

테트로미노가 놓여진 칸들의 점수의 합의 최대값을 구하는 문제이다.

접근방법

브루트포스로 풀었다.

나올 수 있는 모든 도형의 모양을 구하고 (0,0) 기준으로 좌표를 구한다음

모든 도형에 대해 일일이 어디에 두면 가장 큰 값이 나오고, 그 중에 어떤 도형이 가장 큰 값을 내는지 찾았다.

도형은 모두 19개가 나온다.

오답노트

대칭한 도형을 회전한 도형까지 포함하는 것을 간과해서 도형을 2개를 빼먹고 그렸다. 일단 이렇게 AC는 받았고

다른분들 풀이 보니까 ㅜ 모양 빼고 DFS로 구현한 경우가 많았다.

소스코드

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

struct Pos{
    int r;
    int c;
    Pos(int r, int c){
        this->r = r;
        this->c = c;
    }
};

int N, M;
vector<vector<int>> map;
Pos blocks[19][4] = {
    {Pos(0,0), Pos(0,1), Pos(0,2), Pos(0,3)},
    {Pos(0,0), Pos(1,0), Pos(2,0), Pos(3,0)},
    {Pos(0,0), Pos(0,1), Pos(1,0), Pos(1,1)},
    {Pos(0,0), Pos(1,0), Pos(2,0), Pos(2,1)},
    {Pos(0,1), Pos(1,1), Pos(2,1), Pos(2,0)},
    {Pos(0,0), Pos(0,1), Pos(0,2), Pos(1,0)},
    {Pos(0,0), Pos(0,1), Pos(1,0), Pos(2,0)},
    {Pos(0,0), Pos(0,1), Pos(1,1), Pos(2,1)},
    {Pos(0,2), Pos(1,0), Pos(1,1), Pos(1,2)},
    {Pos(0,0), Pos(1,0), Pos(1,1), Pos(2,1)},
    {Pos(0,1), Pos(1,1), Pos(1,0), Pos(2,0)},
    {Pos(0,1), Pos(0,2), Pos(1,0), Pos(1,1)},
    {Pos(0,0), Pos(0,1), Pos(1,1), Pos(1,2)},
    {Pos(0,1), Pos(1,0), Pos(1,1), Pos(1,2)},
    {Pos(0,1), Pos(1,0), Pos(1,1), Pos(2,1)},
    {Pos(0,0), Pos(1,0), Pos(2,0), Pos(1,1)},
    {Pos(0,0), Pos(0,1), Pos(0,2), Pos(1,1)},
    {Pos(0,0), Pos(1,0), Pos(1,1), Pos(1,2)},
    {Pos(0,0), Pos(0,1), Pos(0,2), Pos(1,2)}
};


int main(){
    //input

    cin >> N >> M;
    map.resize(N);
    for(int i = 0 ; i < N ; i++)
        map[i].resize(M);
    
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            cin >> map[i][j];
        }
    }
    
    //process
    
    int result = 0;
    //한 블록씩 계산
    for(int b = 0 ; b < 19 ; b++){
        //맵 어디에 두어야 최대값인지 구하기
        int max = 0;
        //sr, sc : 시작점
        for(int sr = 0 ; sr < N ; sr++){
            for(int sc = 0 ; sc < M ; sc++){
                //sr,sc에서 시작하는 한 블록 점수 계산
                int sum = 0;
                for(int i = 0 ; i < 4 ; i++){
                    Pos here = Pos(sr + blocks[b][i].r, sc + blocks[b][i].c);
                    if(here.r < 0 || here.r > N-1){
                        sum = 0;
                        break;
                    }
                    if(here.c < 0 || here.c > M-1){
                        sum = 0;
                        break;
                    }
                    sum += map[here.r][here.c];
                }
                if(sum > max){
                    max = sum;
                }
            }
        }
        if(result < max){
            result = max;
        }
    }
    
    //output
    cout << result;
    
    return 0;
}