[백준] 14500번 테트로미노

14500번: 테트로미노

모양별로 나올 수 있는 모든 경우를 그려보고

중복되는 부분만 연산으로 저장해두려다 이렇게 푸는 게 아닌 거 같아서 검색해보니

 

이 4가지 도형을 회전, 대칭시킨 모든 경우가

DFS로 깊이 4만큼 탐색하는 경우와 같다는 것을 알게 되었다. (개소름)

 

나머지 도형 하나는 중앙 칸을 기준으로

하좌우, 상좌우, 상하우, 상하좌

로 뻗어있는 모양을 가질 수 있고

이 4가지의 경우의 수는 상하좌우를 순서 상관없이 3가지를 뽑은 경우이므로

조합으로 구해주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, Max;
int arr[500][500], dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
bool visited[500][500] = { false };
void Dfs(int X, int Y, int cnt, int res) {
	if (cnt == 4) Max = max(Max, res);
	else {
		for (int i = 0; i < 4; i++) {
			int x = X + dx[i], y = Y + dy[i];
			if (x >= 0 && x < N && y >= 0 && y < M && !visited[x][y]) {
				visited[x][y] = true;
				Dfs(x, y, cnt + 1, res + arr[x][y]);
				visited[x][y] = false;
			}
		}
	}
}
void Combination(int X, int Y, int idx, int cnt, int res) {
	if (cnt == 3) Max = max(Max, res);
	else {
		for (int i = idx; i < 4; i++) {
			int x = X + dx[i], y = Y + dy[i];
			if (x >= 0 && x < N && y >= 0 && y < M) {
				Combination(X, Y, i + 1, cnt + 1, res + arr[x][y]);
			}
		}
	}
}
int main() {
	cin >> N >> M;
	for (int n = 0; n < N; n++) for (int m = 0; m < M; m++) cin >> arr[n][m];
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			visited[n][m] = true;
			Dfs(n, m, 1, arr[n][m]);
			visited[n][m] = false;
			Combination(n, m, 0, 0, arr[n][m]);
		}
	}
	cout << Max;
	return 0;
}