<Baekjoon> #14500 DFS_테트로미노 c++

#14500 테트로미노

처음에는 문제를 보고 모든 테트로미노의 모양을 구해야 하는 아이디어밖에 떠오르지 않았다. 그래서 다른 사람들의 풀이를 많이 참고했다.
(실제로 어떤 사람은 모든 경우의 수를 구한 사람도 보았다)

먼저 테트로미노를 보면 ㅜ 이 모양 이외에는 깊이가 4인 모양임을 알 수 있다 (테트로미노를 대칭시키고 회전을 시킬 수 있다고 했으므로)

1. DFS 함수
   DFS 함수의 파라미터로는 int y, int x, int depth, int sum 를 둔다. y,x는 모든 정점에서 DFS를 구하기 위함이고 depth와 sum은 depth=4에 이르렀을 때, sum과 maxSum을 비교하여 maxSum을 구하기 위함이다.

2. 모든 정점에서 DFS를 구한다

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = true;
			---DFS 함수 호출---
			visited[i][j] = false;
			---DFS로 구할 수 없는 ㅜ 모양---
		}
	}

//DFS 함수 내
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

for (int i = 0; i < 4; i++) {
	int nx_y = y + dy[i];
	int nx_x = x + dx[i];
    .....
}

3. ㅜ 모양을 구하는 함수
   void extraordinaryShape(int y, int x)
   함수 내에서 ㅏ,ㅓ,ㅗ,ㅜ 의 모양일 때 maxSum을 구하는 경우를 작성

전체코드

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
const int MAX = 501;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m;
int tetro[MAX][MAX];
bool visited[MAX][MAX];
int maxSum = -0x7fffffff;

void dfs(int y, int x, int depth, int sum) {
	if (depth == 4) {
		maxSum = max(sum, maxSum);
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nx_y = y + dy[i];
		int nx_x = x + dx[i];

		if (nx_y<0 || nx_x<0 || nx_y>=n || nx_x>=m) continue;
		if (!visited[nx_y][nx_x]) {
			visited[nx_y][nx_x] = true;
			dfs(nx_y, nx_x, depth + 1, sum + tetro[nx_y][nx_x]);
			visited[nx_y][nx_x] = false;
		}
	}
}

void extraordinaryShape(int y, int x) {
	int sum = 0;
	//ㅏ
	if (y+2<n && x+1<m) {
		sum = tetro[y][x] + tetro[y + 1][x] + tetro[y + 1][x + 1] + tetro[y + 2][x];
		maxSum = max(maxSum, sum);
	}
	//ㅗ
	if (y-1>=0 && x+2<m ) {
		sum = tetro[y][x] + tetro[y][x+1] + tetro[y][x +2] + tetro[y-1 ][x+1];
		maxSum = max(maxSum, sum);
	}
	//ㅓ
	if (y-1>=0 && y+1 <n && x+1 <m) {
		sum = tetro[y][x] + tetro[y ][x+1] + tetro[y -1][x + 1] + tetro[y +1][x+1];
		maxSum = max(maxSum, sum);
	}
	//ㅜ
	if (y+1<n && x+2<m) {
		sum = tetro[y][x] + tetro[y][x+1] + tetro[y][x + 2] + tetro[y+1][x+1];
		maxSum = max(maxSum, sum);
	}
}

int main() {
	memset(visited, false, sizeof(visited));
	cin >> n >> m;
	for (int i = 0; i < n; i++) 		
		for (int j = 0; j < m; j++) 
			cin >> tetro[i][j];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = true;
			dfs(i, j, 1, tetro[i][j]);
			visited[i][j] = false;
			extraordinaryShape(i, j);
		}
	}
	cout << maxSum << endl;
	return 0 ;
}