[Algorithm] Baekjoon 14500번 : 테트로미노

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

14500번: 테트로미노

int board[501][501] = { 0 };
bool visited[501][501] = { false };
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
int row = 0;
int col = 0;
int maxNum = 0;
 
void DFS(int curY, int curX, int sum, int depth)
{
    sum += board[curY][curX];
 
    if (depth == 3)
    {
        maxNum = max(maxNum, sum);
        return;
    }
 
    for (int i = 0; i < 4; i++)
    {
        int nextY = curY + dir[i][0];
        int nextX = curX + dir[i][1];
 
        if (nextY < 0 || nextY >= row) continue;
        if (nextX < 0 || nextX >= col) continue;
        if (visited[nextY][nextX]) continue;
 
        visited[nextY][nextX] = true;
        DFS(nextY, nextX, sum, depth + 1);
        visited[nextY][nextX] = false;
    }
}
 
void shapeOne(int curY, int curX)
{
    int sum = board[curY][curX] + board[curY + 1][curX - 1] + board[curY + 1][curX] + board[curY + 1][curX + 1];
    maxNum = max(maxNum, sum);
}
 
void shapeTwo(int curY, int curX)
{
    int sum = board[curY][curX] + board[curY][curX + 1] + board[curY][curX + 2] + board[curY + 1][curX + 1];
    maxNum = max(maxNum, sum);
}
 
void shapeThree(int curY, int curX)
{
    int sum = board[curY][curX] + board[curY + 1][curX] + board[curY + 1][curX + 1] + board[curY + 2][curX];
    maxNum = max(maxNum, sum);
}
 
void shapeFour(int curY, int curX)
{
    int sum = board[curY][curX] + board[curY + 1][curX - 1] + board[curY + 1][curX] + board[curY + 2][curX];
    maxNum = max(maxNum, sum);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> row >> col;
 
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            cin >> board[i][j];
        }
    }
 
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            visited[i][j] = true;
            DFS(i, j, 0, 0); // ㅗ모양 제외 전부 체크.
            visited[i][j] = false;
 
            if (i + 1 < row && j - 1 >= 0 && j + 1 < col) shapeOne(i, j);
            if (i + 1 < row && j + 2 < col) shapeTwo(i, j);
            if (i + 2 < row && j + 1 < col) shapeThree(i, j);
            if (j - 1 >= 0 && i + 2 < row) shapeFour(i, j);
        }
    }
 
    cout << maxNum;
 
    return 0;
}

 

블럭의 모양들은 규칙이 있다.

ㅗ자를 제외한 블럭들은, 특정 점을 기준으로 DFS를 돌렸을 시 4번째 depth에서 멈췄을 때의 모양과 동일하다.

4번째 depth인 이유는 모든 블럭이 4칸짜리이기 때문이다.

물론 이 가정은 이번 문제처럼 회전,대칭이 가능하다는 전제하에서다.

 

그렇기 때문에 모든 위치노드들에 대해서 depth를 4까지 돌렸을 때의 값들을 이용해 maxNum을 갱신시켜준다.

 

ㅗ자 블럭은 위의 가정이 통하지 않기때문에 하나씩 모양을 구현해준다. 

다행히 블럭 특성상 회전하는 4가지 경우에 대칭하는 경우까지 포함되어있기 때문에 4가지의 회전하는 4가지의 경우만 고려해주면 된다.