[백준/C++] 14500 - 테트로미노(브루트 포스)

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

풀이 참고

브루트 포스

모든 테트로미노 모양에 대해 합을 구해보고, 그 중에서 제일 큰 값을 고르는 문제이다. 특별한 공식이나 꼼수 없이 모든 케이스를 실행해봐야 하기 때문에 브루트 포스에 해당된다.

좌표 배열

좌표 배열은 x좌표, y좌표 기준 얼마나 움직일지를 저장해놓는 배열이다.

테트로미노의 경우 4칸으로 이루어져 있기 때문에, 총 4개의 (x, y) 좌표가 필요하다. 또한 문제에 제시된 5개의 모양을 회전하고, 대칭시키면 총 19개의 모양이 생긴다.

처음엔 4개의 좌표를 배열에 저장하려고 했는데, 다른 문제 풀이를 참고한 결과 기준점을 제외한 3개의 좌표만 저장하는게 더 간단하겠다 싶어서 그렇게 구현해봤다. 따라서 int tetro[19][3][2]로 배열을 선언해주고, 그 안에는 {{1,0}, {2,0}, {3,0}} 과 같이 y, x 좌표값을 순서대로 넣어준다. (문제에서 입력받는 n, m이 세로, 가로이기 때문에 여기서도 y, x 순으로 저장해준다.)

로직

for (int k = 0; k < 19; k++) {
    int sum = nums[i][j];
    bool is_valid = true;
    for (int l = 0; l < 3; l++) {
            int ny = i + tetro[k][l][0];
            int nx = j + tetro[k][l][1];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) {
                is_valid = false;
                break;
        }
        sum += nums[ny][nx];
    }
    if (is_valid && sum > current_max) current_max = sum;
}

19가지 모양에 대해 각각 숫자의 합을 구해야 한다. 그래서 sum 변수를 선언해주고(0으로 초기화도 해주고), 먼저 기준점인 nums[i][j] 값을 sum에 더해준다.

그 다음 기준점을 가지고 tetro 배열 안에 있는 3개의 좌표만큼 이동한다. 만약 이동한 좌표가 nxm 배열을 벗어나면 스킵한다. 모두 유효한 경우, 4칸의 숫자를 sum에 모두 더해준다.

이후 current_max 값보다 이번 sum값이 크다면 업데이트 해주면 된다.

전체 코드

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int> > nums(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> nums[i][j];

    int tetro[19][3][2] = {
        { {1,0}, {2,0}, {3,0} },
        { {0,1}, {0,2}, {0,3} },
        { {1,0}, {0,1}, {1,1} },
        { {1,0}, {2,0}, {2,-1} },
        { {1,0}, {2,0}, {2,1} },
        { {0,1}, {0,2}, {1,0} },
        { {0,1}, {0,2}, {1,2} },
        { {0,1}, {1,0}, {2,0} },
        { {0,1}, {1,1}, {2,1} },
        { {1,0}, {1,1}, {1,2} },
        { {0,1}, {0,2}, {-1,2} },
        { {1,0}, {1,-1}, {2,-1} },
        { {1,0}, {1,1}, {2,1} },
        { {0,1}, {-1,1}, {-1,2} },
        { {0,1}, {1,1}, {1,2} },
        { {0,1}, {-1,0}, {0,-1} },
        { {-1,0}, {0,-1}, {1,0} },
        { {0,-1}, {1,0}, {0,1} },
        { {1,0}, {0,1}, {-1,0} }
    };

    int current_max = 0;
    for (int i = 0; i < n; i++) {    
        for (int j = 0; j < m; j++) { 
            for (int k = 0; k < 19; k++) {
                int sum = nums[i][j];
                bool is_valid = true;
                for (int l = 0; l < 3; l++) {
                    int ny = i + tetro[k][l][0];
                    int nx = j + tetro[k][l][1];
                    if (ny < 0 || ny >= n || nx < 0 || nx >= m) {
                        is_valid = false;
                        break;
                    }
                    sum += nums[ny][nx];
                }
                if (is_valid && sum > current_max) current_max = sum;
            }
        }
    }
    cout << current_max << endl;
    return 0;
}