[Baekjoon] 14500번: 테트로미노

🥅 문제

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

 

🔍 설계

처음에는 시작 좌표를 잡고, 그 좌표에서 시작하는 테트로미노 케이스를 모두 만들어서 값을 도출하려 했으나, 대칭과 회전까지 고려했을 때, 케이스가 너무 많아진다.

 

테트로미노의 특징은 인접한 칸으로 이루어져 있다는 것이다. 따라서, DFS를 이용하여 4개의 칸으로 이루어진 테트로미노를 만들 수 있다. (poli)

 

하지만, ㅗ 모양의 테트로미노는 인접한 칸으로 확장해나가는 DFS로 구할 수 없으므로, 따로 만들어야 한다. ㅗ 모양을 만드는 가장 쉬운 방법은 十 모양의 테트로미노를 만들고, 상하좌우에서 하나씩 빼면 된다. 十 모양을 구성하는데, 칸이 존재할 수 있는 범위를 벗어나는 경우에는 제외되었다고 생각하면 되고, 제외된 모양이 ㅗ 모양을 이룰 때를 대비하여 그대로 갱신 시도를 하고, ㅗ 모양을 못 이루었다면 poli에서 갱신할 수 있으므로 괜찮다.

 

👊 풀이

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

int n, m, result = 0;
vector<vector<int>> paper(500, vector<int>(500));
vector<vector<bool>> visited(500, vector<bool>(500));
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };


void poli(int x, int y, int count, int sum) {
	if (count == 4) {
		result = max(result, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int new_x = x + dx[i];
		int new_y = y + dy[i];
		if (!(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m)) {
			continue;
		}
		if (!visited[new_x][new_y]) {
			visited[new_x][new_y] = true;
			poli(new_x, new_y, count + 1, sum + paper[new_x][new_y]);
			visited[new_x][new_y] = false;
		}
	}
}

void poli2(int x, int y) {
	int temp_result = paper[x][y];
	for (int i = 0; i < 4; i++) {
		int new_x = x + dx[i];
		int new_y = y + dy[i];
		if (!(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m)) {
			continue;
		}
		temp_result += paper[new_x][new_y];
	}
	for (int i = 0; i < 4; i++) {
		int new_x = x + dx[i];
		int new_y = y + dy[i];
		if (!(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m)) {
			result = max(result, temp_result);
			continue;
		}
		result = max(result, temp_result - paper[new_x][new_y]);
	}
}

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> paper[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = true;
			poli(i, j, 1, paper[i][j]);
			visited[i][j] = false;

			poli2(i, j);
		}
	}
	cout << result << "\n";
	return 0;
}