[C++] 백준 14500 테트로미노

#include <iostream>
#include <vector>
#include <algorithm>
 
int N = 0;
int M = 0;
int graph[501][501] = {};
int iDirX[4] = {1, -1, 0, 0};
int iDirY[4] = { 0,0, 1,-1 };
bool visit[501][501] = {};
int iAnswer = 0;
 
void DFS(int iX, int iY, int iCount, int iSum) 
{
	if (iCount == 4)
	{
		iAnswer = std::max(iAnswer, iSum);
		return;
	}
 
	for (int i = 0; i < 4; ++i) 
	{
		int iNextX = iX + iDirX[i];
		int iNextY = iY + iDirY[i];
 
		if (iNextX >= 0 && iNextX < N &&
			iNextY >= 0 && iNextY < M)
		{
			if (!visit[iNextX][iNextY])
			{
				visit[iNextX][iNextY] = true;
				DFS(iNextX, iNextY, iCount + 1, iSum + graph[iNextX][iNextY]);
				visit[iNextX][iNextY] = false;
			}
		}
	}
 
 
	if (iX - 1 >= 0 && iY - 1 >= 0 && iX + 1 < N)
	{
		iAnswer = std::max(iAnswer, graph[iX - 1][iY] + graph[iX][iY - 1] + graph[iX][iY] + graph[iX + 1][iY]);
	}
 
	if (iX - 1 >= 0 && iY + 1 < M && iX + 1 < N)
	{ 
		iAnswer = std::max(iAnswer, (graph[iX - 1][iY] + graph[iX][iY + 1] + graph[iX][iY] + graph[iX + 1][iY]));
	}
 
	if (iY - 1 >= 0 && iY + 1 < M && iX + 1 < N)
	{
		iAnswer = std::max(iAnswer, (graph[iX][iY] + graph[iX + 1][iY] + graph[iX + 1][iY - 1] + graph[iX + 1][iY + 1]));
	}
 
	if (iY - 1 >= 0 && iY + 1 < M && iX + 1 < N)
	{
		iAnswer = std::max(iAnswer, (graph[iX][iY - 1] + graph[iX][iY] + graph[iX][iY + 1] + graph[iX + 1][iY]));
	}
}
 
int main() 
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	std::cin >> N >> M;
 
	for (int i = 0; i < N; ++i) 
	{
		for (int j = 0; j < M; ++j) 
		{
			std::cin >> graph[i][j];
		}
	}
 
	for (int i = 0; i < N; ++i) 
	{
		for (int j = 0; j < M; ++j) 
		{
			visit[i][j] = true;
			DFS(i, j, 1, graph[i][j]);
			visit[i][j] = false;
 
		}
	}
 
	std::cout << iAnswer;
 
	return 0;
}

처음에는 모든 곳을 넣어줘서 가장 큰 수를 구해줘야하는 지 알았는데 아니었습니다....

 

 딱 한가지 가장 큰 수만 구하면 됩니다.

 모든 크기가 기본으로 4입니다. 그렇기 때문에 한가지를 제외하고는 경로탐색을 이용해서 풀 수 있습니다.

제외한 한가지를 빼고는 모두 DFS를 이용해서 풉니다. (경로를 기억하면서 풀기 위해서 DFS를 사용했습니다.)

다음에 다시 사용하기 위해서 방문한 visit을 false해줘야 합니다.

제외한 ㅏ 모양은 DFS로 풀 수 없기 때문에 경로를 따로 입력해서 구해줍니다.