[BOJ_C++] 14500번 : 테트로미노

code

#include <bits/stdc++.h>

using namespace std;

int dx[4] ={-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int board[500][500];
bool visited[500][500];
int MAX, n, m;

void ufind(int y, int x){
    // ㅜ, ㅗ, ㅏ, ㅓ 순서
    if(y + 1 < n && x + 2 < m)
        MAX = max(MAX, board[y][x] + board[y][x + 1] + board[y][x + 2] + board[y + 1][x + 1]);
    if (y - 1 >= 0 && x + 2 < m)
        MAX = max(MAX, board[y][x] + board[y][x + 1] + board[y][x + 2] + board[y - 1][x + 1]);
    if (y + 2 < n && x + 1 < m)
        MAX = max(MAX, board[y][x] + board[y + 1][x] + board[y + 2][x] + board[y + 1][x + 1]);
    if (y + 2 < n && x - 1 >= 0)
        MAX = max(MAX, board[y][x] + board[y + 1][x] + board[y + 2][x] + board[y + 1][x - 1]);
}

void normalfind(int y, int x, int depth, int sum){
    if(depth == 3)
        MAX = max(MAX, sum);
    else{
        for(int i=0; i<4; i++){
            int ny, nx;
            ny = y + dy[i], nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            if(visited[ny][nx]) continue;
            visited[ny][nx] = true;
            normalfind(ny, nx, depth + 1, sum + board[ny][nx]);
            visited[ny][nx] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(visited, false, sizeof(visited));
    cin >> n >> m;

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> board[i][j];
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++)
        {
            ufind(i, j);
            visited[i][j] = true;
            normalfind(i, j, 0, board[i][j]);
            visited[i][j] = false;
        }
    }

    cout << MAX;

    return 0;
}

• 아래 4가지 폴리오미노는 시작부터 깊이 3을 만족하면 된다.

• 그러나 다음 그림은 특수한 경우로 모든 경우를 다 검사해야 한다.

• 따라서 위 4가지 는 normalfind() 함수로, 나머지 특수한 경우는 ufind로 찾아주었다.
• normalfind()는 깊이가 3이 될 때까지 현재의 전 합에 현재의 보드 값을 더해나간다. 이후 깊이가 3이 되면 기존 MAX와 현재 sum을 비교하여 더 큰 값을 저장한다.
• ufind()는 ㅜ, ㅗ, ㅏ, ㅓ의 모습을 모두 검사하며 가장 큰 값을 저장하게 된다.
• 보드의 모든 위치가 깊이 0(시작점)이 되도록 설정하여 가질수 있는 가장 큰 값을 저장하였다.

결과