[백준 14500] 테트로미노

🔗알고리즘 문제

예외 처리 해줄것이 많고 발상이 쉽지 않아 어려웠던 문제. 그래도 혼자 힘으로 해결할 수 있어서 풀고 난 후 내 자신이 대견했다 ^_^

문제 분석

이 문제는 각각의 칸마다 수들이 적혀있고 이 보드판에 테트로미노 도형을 하나 둘 때 놓여진 자리에 수가 가장 큰 경우를 구하는 문제이다.

발상 & 알고리즘 설계

브루트포스를 사용하여 도형의 모든 모양을 완전탐색해주면 쉽게 해결할 수 있을 것 같았지만 대칭, 회전까지 포함하여 총 19가지의 경우를 모두 구현하자니 구현할 양이 너무 많아보였다..

다른 방법이 없을가 하여 문제를 보던 중 도형들은 원점에서 시작하여 깊이가 4인 DFS를 사용하여 탐색할 수 있겠다고 생각하였다.

void DFS(int x, int y, int depth, int sum)
{
    if(depth >= 3)
    {
        answer = max(answer, sum);
        return;
    }

    for(int i = 0; i < 4; i++)
    {
        int _x = x + destX[i];
        int _y = y + destY[i];

        if(_x < 0 || _x > m - 1 || _y < 0 || _y > n - 1)
            continue;

        if(check[_y][_x] == true)
            continue;
        
        check[_y][_x] = true;
        DFS(_x, _y, depth + 1, sum + board[_y][_x]);
        check[_y][_x] = false;
    }
}

원점으로부터 깊이가 4일때까지 탐색하고 그 중 가장 큰 수가 나오는 경우를 저장한다.

하지만 이런방식으로는 ㅗ ㅜ ㅏ ㅓ 블럭을 탐색하지 못하였다. 해당 블럭만 예외처리를 해주어 DFS를 사용하지 않고 따로 탐색해 문제를 해결할 수 있었다.

코드

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int destX[4] = { 1, -1, 0, 0 };
int destY[4] = { 0, 0, -1, 1 };

int board[501][501] = {};
int check[501][501] = {};

int n;
int m;

int answer = 0;

void DFS(int x, int y, int depth, int sum)
{
    if(depth >= 3)
    {
        answer = max(answer, sum);
        return;
    }

    for(int i = 0; i < 4; i++)
    {
        int _x = x + destX[i];
        int _y = y + destY[i];

        if(_x < 0 || _x > m - 1 || _y < 0 || _y > n - 1)
            continue;

        if(check[_y][_x] == true)
            continue;
        
        check[_y][_x] = true;
        DFS(_x, _y, depth + 1, sum + board[_y][_x]);
        check[_y][_x] = false;
    }
}

void specialShape(int x, int y)
{
    priority_queue<int> vals;
    int sum = board[y][x];

    for(int i = 0; i < 4; i++)
    {
        int _x = x + destX[i];
        int _y = y + destY[i];

        if(_x < 0 || _x > m - 1 || _y < 0 || _y > n - 1)
            continue;

        vals.push(board[_y][_x]);
    }

    if(vals.size() >= 3)
    {
        for(int i = 0; i < 3; i++)
        {
            sum += vals.top();
            vals.pop();
        }
        answer = max(answer, sum); 
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(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++)
        {
            check[i][j] = true; 
            DFS(j, i, 0, board[i][j]);
            specialShape(j, i);
            check[i][j] = false;
        }
    }

    cout << answer;
}