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

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

14500번: 테트로미노

 

문제를 보면 4개의 이어지는 칸의 합이 최대인 값을 구하면 됩니다.

 

 

우리가 사용할 수 있는 모양을 보면 테트리스 조각이랑 똑같은데 T블록( ㅗ블록) 을 제외한 나머지 블록들은 간단히 DFS를 사용하면 모든 경우를 구할 수 있습니다.

 

T블록의 경우는 따로 분리해서 코드를 작성해주면 됩니다.

 

각 칸의 숫자는 1000을 넘지 않는 자연수이므로 int 범위에서도 충분합니다.

 

#include<iostream>
#include<utility>

using namespace std;
using ll = long long;

int board[501][501];
bool visited[501][501];
pair<int, int>dir[4] = { {1,0},{0,1}, {-1,0} ,{0,-1} };
int n, m;

int dfs(int x, int y, int depth) {
    if (depth == 4) return board[x][y];
    int ret = 0;
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i].first;
        int ny = y + dir[i].second;

        if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny]) {
            ret = max(ret, dfs(nx, ny, depth + 1));
            visited[nx][ny] = false;
        }
    }
    visited[x][y] = false;
    return board[x][y] + ret;
}

int TBlock(int x, int y) { // T블럭은 따로 분리하여 작성
    int ret = 0;
    if (x + 1 < n && y - 1 >= 0 && y + 1 < m)
        ret = max(ret, board[x][y] + board[x + 1][y] + board[x][y - 1] + board[x][y + 1]);//ㅜ
    if (x + 1 < n && x - 1 >= 0 && y + 1 < m)
        ret = max(ret, board[x][y] + board[x + 1][y] + board[x - 1][y] + board[x][y + 1]);//ㅏ
    if (x - 1 >= 0 && y - 1 >= 0 && y + 1 < m)
        ret = max(ret, board[x][y] + board[x - 1][y] + board[x][y - 1] + board[x][y + 1]);//ㅗ
    if (x + 1 < n && x - 1 >= 0 && y - 1 >= 0)
        ret = max(ret, board[x][y] + board[x + 1][y] + board[x - 1][y] + board[x][y - 1]);//ㅓ
    return ret;
}

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

    int ans = 0;
    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++) {
            ans = max(ans, dfs(i, j, 1));
            ans = max(ans, TBlock(i, j));
        }
    }
    cout << ans;
    
    return 0;
}