[백준알고리즘] 14500번: 테트로미노 -C++

[백준알고리즘] 14500번: 테트로미노 -C++

14500번: 테트로미노 (acmicpc.net)

14500번: 테트로미노

다 풀고 나니 DFS니 BFS니 뭐 다양하게 풀 수 있는 경우가 있는 것 같다. 근데 그런 것들은 어떻게 하라는 건지 이해를 잘 못하는 바람에 다른 풀이를 직접 해보지는 못했다.

 

예전에 파이썬으로 풀었던 문제인데, 포스팅은 하지 않았다. 풀고나서 파이썬 코드를 보니까 뭔 코드인지 전혀 못 알아먹겠어서 같이 첨부하지도 못할 것 같다. ㅋㅋㅋㅋ

 

이래서 네이밍이 중요하고, 주석이 중요한 것 같다.. 코드 자체는 간결한데 이해를 못 하겠다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

앞서 말했듯이, 나는 DFS나 BFS로 푸는 풀이에 대해서는 간단하게 스윽 살펴보니 뭐라고 하는지 정확히 모르겠어서 그냥 완전 탐색(Bruteforce) 방식을 사용했다.

 

먼저, 가능한 폴리오미노 블럭의 모양을 벡터로 저장시켜주었다. 따라서 각 블록을 나타내는데 2차원 벡터가 필요하기 때문에 그러한 블록을 나열하는 벡터가 필요하기 때문에 3차원 벡터를 사용했다.

 

이후, 주어진 점수판에서 각 지점을 순차적으로 탐색하면서 폴리오미노 블럭을 놓았을 때 가장 높은 점수가 나오는 경우를 찾았다. 이때 각 지점은 폴리오미노의 왼쪽 상단의 지점에 위치한다고 가정했다.

 

그리고 문제를 풀면서 애매했던 부분이 있었고, 이 부분 때문에 한 번 틀렸었다.

바로 각 폴리오미노 블럭을 회전시킨 경우만 존재하는 것이 아니라, 대칭시킨 경우도 존재한다는 것이다.

 

이 부분만 해결해주니 나머지는 손쉽게 해결할 수 있었다. 각 지점에서 놓을 수 있는 폴리오미노 블록을 찾고, 해당 폴리오미노 블록들 중 가장 큰 점수를 얻는 값을 찾는다. 그리고 그렇게 얻은 점수들 가운데 또다시 가장 큰 점수를 찾으면 그 값이 답이다.

폴리오미노 블럭을 놓을 때 범위 계산만 잘해주면 쉽게 풀 수 있는 문제였다.

 

아래 코드는 위의 풀이대로 푼 완전 탐색 코드다. 처음에 폴리오미노 블록들을 나열하는 것 때문에 코드가 길어졌다.

#include <iostream>
#include <vector>

std::vector<std::vector<std::vector<bool>>> polyominos = {
	{
		{1, 1, 1, 1}
	},
	{
		{1},
		{1},
		{1},
		{1}
	},
	{
		{1, 1},
		{1, 1}
	},
	{
		{1, 1, 1},
		{1, 0, 0}
	},
	{
		{1, 0, 0},
		{1, 1, 1},
	},
	{
		{1, 1},
		{0, 1},
		{0, 1}
	},
	{
		{1, 1},
		{1, 0},
		{1, 0}
	},
	{
		{0, 0, 1},
		{1, 1, 1}
	},
	{
		{1, 1, 1},
		{0, 0, 1}
	},
	{
		{1, 0},
		{1, 0},
		{1, 1}
	},
	{
		{0, 1},
		{0, 1},
		{1, 1}
	},
	{
		{1, 0},
		{1, 1},
		{0, 1}
	},
	{
		{0, 1},
		{1, 1},
		{1, 0}
	},
	{
		{0, 1, 1},
		{1, 1, 0}
	},
	{
		{1, 1, 0},
		{0, 1, 1}
	},
	{
		{1, 1, 1},
		{0, 1, 0},
	},
	{
		{0, 1},
		{1, 1},
		{0, 1}
	},
	{
		{0, 1, 0},
		{1, 1, 1}
	},
	{
		{1, 0},
		{1, 1},
		{1, 0}
	}
};

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

int getSum(const std::vector<std::vector<int>>& map, int x, int y)
{
	int height = map.size();
	int weight = map[0].size();

	int maxSum = 0;

	for (auto polyomino : polyominos)
	{
		int blockHeight = polyomino.size();
		int blockWeight = polyomino[0].size();

		if (height < y + blockHeight || weight < x + blockWeight)
			continue;

		int sum = 0;
		for (int i = 0; i < blockHeight; i++)
			for (int j = 0; j < blockWeight; j++)
				sum += (polyomino[i][j] * map[y + i][x + j]);

		maxSum = std::max(maxSum, sum);
	}

	return maxSum;
}

void solve(void)
{
	int n, m;
	std::cin >> n >> m;

	std::vector<std::vector<int>> map(n, std::vector<int>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			std::cin >> map[i][j];


	int maxSum = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			maxSum = std::max(maxSum, getSum(map, j, i));

	std::cout << maxSum;
}