[백준 BOJ][C++]14500번 테트로미노 풀이: 브루트포스 & DFS

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

14500번: 테트로미노

 

 이 문제는 모든 도형이 회전, 대칭한 모든 모양에 대해 그 합을 구해도 되지만, 위 그림 처럼 ㅗ 모양을 제외한 나머지 모양은 depth가 4인 영역을 탐색하여 그 합을 구할 수 있습니다. 

 

 각 종이의 칸마다 DFS를 호출하여 depth가 4만큼 탐색하여 최대 합을 구하여 ㅗ 모양의 합과 비교하면 됩니다. 

 

 ㅗ 모양은 회전하면 총 ㅗ, ㅜ, ㅓ, ㅏ 네가지 모양이 나오므로 4개의 함수를 작성하여 모양에 맞는 합을 구해줍니다. 

 

[풀이 과정]

1. 종이의 각 칸의 방문 여부를 나타내는 visit 배열을 false 값으로 초기화한다. 

2. 종이의 각 칸의 위치 (x, y) 에 대하여 DFS를 호출한다. 

2-1. DFS의 인자는 x, y, sum, depth로 depth가 4가 되면 최종 sum과 비교하여 최댓값을 ans에 저장한 후 종료한다. 

3. ㅗ, ㅜ, ㅓ, ㅏ 모양에 대한 합을 ans와 비교하여 최댓값을 ans에 저장한다. 

4. 종이의 모든 칸에 대해 1~3 과정을 반복한다. 

 

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<cstring>

using namespace std;

int ans;

int n, m;
int map[501][501];
bool visit[501][501] = { false, };

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

void dfs(int x, int y, int sum, int depth) {

	if (depth == 4) {
		ans = max(ans, sum);
		return;
	}

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

		if (tx < 0 || tx >= m || ty < 0 || ty >= n)
			continue;
		if (visit[ty][tx])
			continue;

		visit[ty][tx] = true;
		dfs(tx, ty, map[ty][tx] + sum, depth + 1);
		visit[ty][tx] = false;
	}
}

void shape1(int x, int y) { // ㅜ
	int temp = 0;
	temp = map[y][x] + map[y][x + 1] + map[y][x + 2] + map[y + 1][x + 1];
	ans = max(ans, temp);
}
void shape2(int x, int y) { // ㅗ
	int temp = 0;
	temp = map[y][x] + map[y][x + 1] + map[y - 1][x + 1] + map[y][x + 2];
	ans = max(ans, temp);
}
void shape3(int x, int y) { // ㅏ
	int temp = 0;
	temp = map[y][x] + map[y + 1][x] + map[y + 1][x + 1] + map[y + 2][x];
	ans = max(ans, temp);
}
void shape4(int x, int y) { // ㅓ
	int temp = 0;
	temp = map[y][x] + map[y + 1][x] + map[y + 1][x - 1] + map[y + 2][x];
	ans = max(ans, temp);
}

int main(void) {

	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++) {
			memset(visit, false, sizeof(visit));
			visit[i][j] = true;
			dfs(j, i, map[i][j], 1);
			if (j + 2 < m) {
				if (i + 1 < n)
					shape1(j, i);
				if (i - 1 >= 0)
					shape2(j, i);
			}
			if (i + 2 < n) {
				if (j + 1 < m)
					shape3(j, i);
				if (j - 1 >= 0)
					shape4(j, i);
			}
		}
	}

	cout << ans;

	return 0;
}