백준 14500 : 테트로미노 c++

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int map[501][501];
int temp;
int answer;
bool visited[501][501];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(int depth, int x, int y, int sum){
	visited[x][y] = true;
	
	if(depth == 4){
		if(sum > answer) answer = sum;
		return;
	} 

	for(int i = 0; i < 4; i++){
		if(x+dx[i] >= 0 && x+dx[i] < n && y+dy[i] >= 0 && y+dy[i] < m){
			if(visited[x+dx[i]][y+dy[i]] == false){
				visited[x+dx[i]][y+dy[i]] = true;
				dfs(depth+1, x+dx[i], y+dy[i], sum+map[x+dx[i]][y+dy[i]]);
				visited[x+dx[i]][y+dy[i]] = false;			
			}	
		}
	}
}

void shape1(int r, int c)
{
	int sum = 0;
	sum = map[r][c] + map[r][c + 1] + map[r][c + 2] + map[r - 1][c + 1];
	answer = max(answer, sum);
}

void shape2(int r, int c)
{
	int sum = 0;
	sum = map[r][c] + map[r][c + 1] + map[r][c + 2] + map[r + 1][c + 1];
	answer = max(answer, sum);
}

void shape3(int r, int c)
{
	int sum = 0;
	sum = map[r][c] + map[r + 1][c] + map[r + 2][c] + map[r + 1][c + 1];
	answer = max(answer, sum);
}

void shape4(int r, int c)
{
	int sum = 0;
	sum = map[r][c] + map[r - 1][c + 1] + map[r][c + 1] + map[r + 1][c + 1];
	answer = max(answer, sum);
}

int main(){
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> map[i][j];
		}
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			visited[i][j] = true;
			dfs(1, i, j, map[i][j]);
			visited[i][j] = false;
			if (i - 1 >= 0 && j + 2 < m) shape1(i, j);
			if (j + 2 < m && i + 1 < n) shape2(i, j);
			if (i + 2 < n && j + 1 < m) shape3(i, j);
			if (i + 1 < n && i - 1 >= 0 && j + 1 < m) shape4(i, j);
		}
	}
	
	cout << answer;
	return 0;
}

알게된 점

아니 이걸 어떻게 생각할까?

ㅗ 모양을 제외하고는 깊이 4의 dfs로 풀 수 있다고 구글에서 말해서

그거까진 구현했는데

ㅗ모양을 어떻게 하는지 모르겠어서 그건 구글을 또 봤다.

그냥 빡코딩을 했구나 싶었다..

브루트포스에 대한 조금 깊은 이해가 생겼다.