[백준 14500번] 테트로미노 (C++)

문제링크 : https://www.acmicpc.net/problem/14500

14500번: 테트로미노

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pil pair <int, int>

int arr[500][500], visited[500][500];

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

int N, M, result;

void lastshape(int y, int x)
{
    if(y + 1 < N && x + 2 < M)  // ㅗ
    {
        result = max(result, arr[y][x] + arr[y][x+1] + arr[y][x+2] + arr[y+1][x+1]);
    }
    if(y - 1 >= 0 && x + 2 < M)  // ㅜ
    {
        result = max(result, arr[y][x] + arr[y][x+1] + arr[y][x+2] + arr[y-1][x+1]);
    }
    if(y + 2 < N && x + 1 < M)  // ㅏ
    {
        result = max(result, arr[y][x] + arr[y+1][x] + arr[y+2][x] + arr[y+1][x+1]);
    }
    if(y + 2 < N && x - 1 >=0)  // ㅓ
    {
        result = max(result, arr[y][x] + arr[y+1][x] + arr[y+2][x] + arr[y+1][x-1]);
    }
}

void cal_dfs(int cnt, int sum, int y, int x)  //깊이가 4인 도형들
{
    if(cnt == 3)
    {
        result = max(result, sum);
        return;
    }

    for(int i=0; i<4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
        if(visited[ny][nx]) continue;
        visited[ny][nx] = true;
        cal_dfs(cnt + 1, sum + arr[ny][nx], ny, nx);
        visited[ny][nx] = false;  //방문 초기화
    }
}

void cal_max(int y, int x)
{
    lastshape(y, x);

    visited[y][x] = true;
    cal_dfs(0, arr[y][x], y, x);
    visited[y][x] = false;  //방문 초기화
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M;

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

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cal_max(i, j);
        }
    }

    cout << result;

    return 0;
}

ㅗ 모양 도형을 제외한 나머지 도형들은 전부 깊이가 4이다.

따라서 dfs를 통해서 최대 합을 구할 수 있다.

 

ㅗ 모양 도형의 경우 회전이 가능하기에 경우의 수가 ㅗ, ㅜ, ㅓ, ㅏ 이렇게 4가지이다.

이 4가지에 대해서만 따로 직접 각각의 위치를 더해줌으로써 최대 합을 구한다.

 

완전탐색을 통해 각 위치에 대해 탐색하므로, 한번의 계산과정을 통해 방문처리 해준 것은 다음 값이 탐색을 시작하는 것을 위하여 반드시 방문처리를 풀어줘야 한다.

 

ㅗ 모양 도형으로 계산하는 방법과 같이 나머지 도형도 dfs 없이 없이 저런 노가다로 가능은 하겠으나,, 너무 하드 코딩일 듯 하다.