BaekJoon 14500번: 테트로미노(C++)

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

14500번: 테트로미노

풀이법

1) 배치할 수 있는 총 경우의 수가 19가지가 되므로 일일이 쓰는 것 보다는, DFS 기반의 알고리즘을 활용하는 것이 좋다. 일일이 구현하다가, 지쳐서 다른 분들의 블로그를 찾으니 크기가 'ㅜ'모양을 제외하고는 모두 크기가 4인 DFS로 구현하면 가능하다는 점을 확인할 수 있었다.

2) 재귀 기반의 DFS로 'ㅜ'를 제외한 다른 모양들의 최대 합을 구하려 하였고, 'ㅜ', 'ㅏ', 'ㅓ', 'ㅗ' 4가지의 경우는 직접 일일이 구현을 해주었다. (백준 기준 31% 정도에서 오류가 나는 분들은 여기 부분의 구현에 있어 조건을 제대로 확인했는지를 recheck 한다면 해결할 수 있을 것이라고 생각한다.)

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int n, m;
int arr[501][501];
bool visited[501][501];
int ans = 0;
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
void dfs(int a, int b,int cnt,int sum)
{
	if (cnt == 4)
	{
		ans = max(sum, ans);
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int nextX = a + vx[i];
		int nextY = b + vy[i];
		if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
			continue;
		if (!visited[nextX][nextY])
		{
			visited[nextX][nextY] = true;
			dfs(nextX, nextY,cnt+1,sum+arr[nextX][nextY]);
			visited[nextX][nextY] = false;
		}
	}
}
void tetro(int a, int b)
{
	//4. ㅜ
	if (b + 2 < m && a + 1 < n)
	{
		int sum = 0;
		for (int i = b; i <= b + 2; i++)
				sum += arr[a][i];
		sum += arr[a + 1][b + 1];
		ans = max(ans, sum);
	}
	//5. ㅏ
	if (a + 2 < n && b + 1 < m)
	{
		int sum = 0;
		for (int i = a; i <= a + 2; i++)
			sum += arr[i][b];
		sum += arr[a + 1][b + 1];
		ans = max(ans, sum);
	}
	//6. ㅗ
	if (a -1 >=0 && b + 2 < m)
	{
		int sum = 0;
		for (int i = b; i <= b + 2; i++)
			sum += arr[a][i];
		sum += arr[a -1][b + 1];
		ans = max(ans, sum);
	}
	//7. ㅓ
	if (a+2 < n && b -1 >=0)
	{
		int sum = 0;
		for (int i = a; i <= a + 2; i++)
			sum += arr[i][b];
		sum += arr[a+1][b-1];
		ans = max(ans, sum);
	}
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	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++)
		{
			visited[i][j] = true;
			dfs(i, j,1,arr[i][j]);
			visited[i][j] = false;

			tetro(i, j);// ㅜ ㅏ ㅗ ㅓ
		}
	}
	cout << ans;
}