[BOJ14500] 테트로미노

[BOJ14500] 테트로미노

---

문제 링크

---

문제 설명

• 그림과 같은 테트로미노들을 가중치가 있는 보드판에 놓는다.
• 테트로미노들은 방향전환, 대칭이동 이 가능하다.
• 가중치가 가장 최대가 되는 값 을 구하면 된다.

---

코드 리뷰

• 노가다로 풀다가 이건 아닌거 같다는 생각에 고민을 하다보니 각 점에 대해 그래프 탐색을 진행하고 레벨이 4인 경우 의 최대 가중치의 합을 구하면 되겠다는 생각에 처음에 BFS를 통해서 레벨 4의 좌표에 저장된 누적합중 최대를 구해보았는데, 테케가 틀리게 나왔다.
• 가만 생각해보니 BFS를 통해 레벨 4에 있는 누적합에는 노란색 정사각형 테트로미노와 연보라색 ㅗ 모양 테트로미노 는 포함되지 않았다.
• 연보라색 ㅗ 모양 테트로미노는 그래프 탐색으로 구하기가 너무 어려워서, 그 모양에 대해서는 쌩구현으로 해결하고 노란색 정사각형 테트로미노를 포함한 나머지 테트로미노에 대해서는 모든 경우에 대해 DFS를 통해 레벨 4에 있는 누적합중 최대를 구하면 해결 되었다.
• 처음에 코드를 잘못짜서 시간초과가 나서 최적화까지 고려해야하나 싶었는데, 코드를 단순히 잘못짰던 거였고, 그냥 완전탐색 하면 해결 가능.

---

/* 14500 테트로미노 */
// 아래로 내리면 최신 코드 있어요
#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int MAX = 0;
int board[505][505];
int dc[4] = { 0,0,-1,1 };
int dr[4] = { -1,1,0,0 };
int check[505][505];


int dfs(int x, int y, int idx) {
	if (idx == 4) return board[x][y];
	check[x][y] = 1;
	int ret = 0;
	for (int k = 0; k < 4; k++) {
		int nx = x + dc[k];
		int ny = y + dr[k];
		if (nx >= 0 && nx < N && ny >= 0 && ny < M && check[nx][ny] == 0) {
			ret = max(ret, board[x][y] + dfs(nx, ny, idx + 1));
		}
	}
	check[x][y] = 0;
	return ret;
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &board[i][j]);
		}
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			ans = max(ans, dfs(i, j, 1));
			int x1 = i, y1 = j - 1;
			int x2 = i, y2 = j + 1;
			int x3 = i - 1, y3 = j;
			int x4 = i + 1, y4 = j;
			int result1 = 0, result2 = 0, result3 = 0, result4 = 0;
			if (y1 >= 0 && y2 < M && x4<N) {
				result1 = board[i][j] + board[x1][y1] + board[x2][y2] + board[x4][y4];
			}
			if (y1 >= 0 && y2 < M && x3 >= 0) {
				result2 = board[i][j] + board[x1][y1] + board[x2][y2] + board[x3][y3];
			}
			if (x3 >= 0 && x4 < N && y1 >= 0) {
				result3 = board[i][j] + board[x3][y3] + board[x4][y4] + board[x1][y1];
			}
			if (x3 >= 0 && x4 < N && y2 < M) {
				result4 = board[i][j] + board[x3][y3] + board[x4][y4] + board[x2][y2];
			}
			ans = max(ans, max(result1, max(result2, max(result3, result4))));
		}
	}
	printf("%d", ans);
  return 0;
}

//2019-12-23 재풀이
#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n';
using namespace std;

int N, M;
int board[501][501];
int dc[4] = { 0,0,-1,1 };
int dr[4] = { 1,-1,0,0 };
bool check[501][501];
int MAX, sum;

bool OOB(int n, int m) {
	if (n >= 0 && n < N && m >= 0 && m < M) {
		return true;
	}
	return false;
}

void dfs(int n, int m, int cnt) {
	if (cnt == 4) {
		MAX = max(MAX, sum);
		return;
	}
	for (int k = 0; k < 4; k++) {
		int nn = n + dc[k];
		int mn = m + dr[k];
		if (!check[nn][mn] && OOB(nn,mn)) {
			check[nn][mn] = true;
			sum += board[nn][mn];
			dfs(nn, mn, cnt + 1);
			check[nn][mn] = false;
			sum -= board[nn][mn];
		}
	}
}

int hat(int n, int m) {
	int tmp1, tmp2, tmp3, tmp4;
	tmp1 = tmp2 = tmp3 = tmp4 = board[n][m];
	if (OOB(n - 1, m) && OOB(n, m + 1) && OOB(n + 1, m)) {
		tmp1 += board[n - 1][m] + board[n][m + 1] + board[n + 1][m];
	}
	if (OOB(n - 1, m) && OOB(n, m - 1) && OOB(n + 1, m)) {
		tmp2 += board[n - 1][m] + board[n][m - 1] + board[n + 1][m];
	}
	if (OOB(n - 1, m) && OOB(n, m - 1) && OOB(n, m + 1)) {
		tmp3 += board[n - 1][m] + board[n][m - 1] + board[n][m + 1];
	}
	if (OOB(n, m - 1) && OOB(n + 1, m) && OOB(n, m + 1)) {
		tmp4 += board[n][m - 1] + board[n + 1][m] + board[n][m + 1];
	}
	return max(tmp1, max(tmp2, max(tmp3, tmp4)));
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			check[i][j] = true;
			sum += board[i][j];
			dfs(i, j, 1);
			MAX = max(MAX,hat(i, j));
			sum -= board[i][j];
			check[i][j] = false;
		}
	}
	cout << MAX << endl;
	return 0;
}