백준 14500 테트로미노(c++)

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

14500번: 테트로미노

이 문제는 주어진 배열의 해당하는 값 4개를 더한 값들 중 최댓값을 구해야 하는 문제입니다. 

그렇지만, 예외처리 해줘야 하는 부분이 있습니다. ㅗ,ㅜ,ㅏ,ㅓ와 같은 테트로미노 모양은 DFS탐색이 불가능 합니다. 그래서 따로 함수를 만들어서 처리해줘야 하는 번거로움이 있습니다. 그 외에는 백트래킹으로 접근해서 테트로미노의 칸에 놓은 수들의 합의 최댓값을 구해주면 됩니다. 

더불어, 이 문제는 DFS 탐색으로 보기 어려운게, go 함수의 해당 인덱스를 false처리 해주기 때문에, 모든 경우의 수를 조사하는 백트래킹 문제로 봐야 합니다. 

 

<코드>

#include <iostream>
using namespace std;
int a[501][501];
bool check[501][501];
int n, m;
int mov[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int ans = 0;
void go(int x, int y, int sum, int cnt)
{
    if (cnt == 4)
    {
        if (ans < sum)
            ans = sum;
        return;
    }

    if (x < 0 || x >= n || y < 0 || y >= m)
        return;
    if (check[x][y])
        return;
    check[x][y] = true;
    for (int k = 0; k < 4; k++)
    {
        go(x + mov[k][0], y + mov[k][1], sum + a[x][y], cnt + 1);
    }
    check[x][y] = false;
}