백준 14500 - 테트로미노

문제링크

• 백준 14500

문제 설명

크기가 NxM이고 각 칸 위에 정수가 하나 쓰여 있는 종이가 있다. 이 종이 위에 4칸으로 이루어진 도형을 놓아서 칸에 쓰여 있는 수들의 합을 최대로 하라.

문제 접근

• 제시되어 있는 도형은 총 5가지 있다. 이 5가지 도형을 회전, 대칭 시켜서 놓을 수 있는 경우 중 합이 최대인 경우를 찾으면 된다.
• 제시된 도형들을 가지고 회전, 대칭 시킬 수 있는 모든 경우를 모아보면 4칸으로 만들 수 있는 모든 도형을 의미한다고 생각했다.
  • 볼록할 철 모양의 도형은 한줄로 겹치지 않게 이동할 수 없기 때문에 예외가 되어야 한다.
• 따라서, 이제부터 완전 탐색 문제로 도형을 완성하는 과정을 재귀호출을 통해 구현한다.
  1. NxM 크기의 종이를 좌측 상단(0,0)부터 탐색한다.
  2. 탐색을 시작한 점부터 상, 하, 좌, 우로 이동하며 도형을 완성하면서 정수의 합을 계산한다.
  • 중복되는 경우를 빼기 위해 모든 도형은 가장 좌측 상단에 위치한 칸이 시작지점이 된다.
  • 이 과정에서 시작지점으로 탐색한 곳은 정수값을 -1로 할당해두었는데, 뒤늦게 볼록할 철 모양의 도형을 놓는 경우 시작지점을 고려하지 않게 되면서 정수합을 구할때 -1만큼 잘못된 계산을 하는 것을 확인했다. 따라서, 해당 구문을 주석처리 하였는데 이렇게 되면 지나치게 재귀호출이 많이 된다는 단점이 있어서 개선이 필요하다.

구현1

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

int n, m;
// 상 하 좌 우 이동
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

// 시작지점으로부터 상대좌표로 표현한 모습
// 4개의 type이 있고, 4개의 점으로 이루어져 있으며, 점은 2개의 좌표로 이루어진다.
int mount_shape[4][4][2] = {
	{ {0,0}, {0, 1}, {-1, 1}, {1, 1} },
	{ {0,0}, {0, 1}, {-1, 1}, {0, 2} },
	{ {0,0}, {-1, 0}, {-2, 0}, {-1, 1} },
	{ {0,0}, {0, 1}, {1, 1}, {0, 2} },
};

bool check_valid(int x, int y)
{
	if (x >= 0 && x < n && y >= 0 && y < m)
		return true;
	else
		return false;
}

void set(vector<vector<int>>& map, vector<vector<bool>>& visited, vector<int>& v, int& smax, int x, int y, int cnt)
{
	if (cnt == 4) {
		int sum = 0;
		for (auto ele : v)
			sum += ele;
		if (smax < sum)
			smax = sum;
		return;
	}

	for (int dir = 0; dir < 4; dir++) {
		int next_x = x + dx[dir];
		int next_y = y + dy[dir];

		// 기저사례1: 범위를 벗어나는 경우 스킵
		if (check_valid(next_x, next_y) == false) continue;
		// 기저사례2: 시작지점보다 좌측 상단에 위치하는 경우 스킵
		// if (map[next_x][next_y] == -1) continue;
		// 기저사례3: 방문한 곳일 경우 스킵
		if (visited[next_x][next_y] == true) continue;

		v.push_back(map[x][y]);
		visited[x][y] = true;
		set(map, visited, v, smax, next_x, next_y, cnt + 1);
		visited[x][y] = false;
		v.pop_back();
	}
}

void put_mount(vector<vector<int>>& map, int& smax, int x, int y)
{
	for (int type = 0; type < 4; type++) {
		int sum = 0;
		bool flag = true;
		for (int dir = 0; dir < 4; dir++) {
			int next_x = x + mount_shape[type][dir][0]; // x좌표
			int next_y = y + mount_shape[type][dir][1]; // y좌표
			if (check_valid(next_x, next_y) == false) {
				flag = false; // 4칸을 못채운 경우
				break;
			}
			sum += map[next_x][next_y];
		}
		if (flag && (smax<sum))
			smax = sum;
	}
}

// 모든 좌표를 탐색하여 테트로미노를 놓았을 때 최대합을 출력한다.
void cover(vector<vector<int>>& map)
{
	vector<vector<bool>> visited(n, vector<bool>(m, false));
	vector<int> v;
	int smax = 0;

	for (int r = 0; r < n; r++) {
		for (int c = 0; c < m; c++) {
			set(map, visited, v, smax, r, c, 0);
			put_mount(map, smax, r, c);
			// map[r][c] = -1; // 시작지점을 -1로 세팅하는 경우 문제 발생 인지
		}
	}
	cout << smax << endl;
	return;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	cin >> n >> m;
	vector<vector<int>> map(n, vector<int>(m, 0));
	for (int r = 0; r < n; r++)
		for (int c = 0; c < m; c++)
			cin >> map[r][c];

	cover(map);
	return 0;
}

구현2

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#define MAX_N_M 500
#define TETROMINO 4
using namespace std;

int board[MAX_N_M][MAX_N_M];
int N, M;
int visited[MAX_N_M][MAX_N_M];
// 출발지점을 포함하는 방향 설정
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, -1, 1 };
int mountShape[4][4][2] = {
	{ {0, 0}, {0, 1}, {1, 1}, {0, 2} },
	{ {0, 0}, {0, 1}, {-1, 1}, {1, 1} },
	{ {0, 0}, {0, 1}, {-1, 1}, {0, 2} },
	{ {0, 0}, {1, 0}, {1, 1}, {2, 0} },
};

int getSum(vector<pair<int, int>> list) {
	int ret = 0;
	for (auto ele : list) {
		ret += board[ele.first][ele.second];
	}
	return ret;
}

int dfs(int xpos, int ypos, vector<pair<int, int>>& cand) {
	if (cand.size() == TETROMINO) {
		return getSum(cand);
	}
	int ret = 0;
	for (int dir = 0; dir < 5; dir++) {
		int nx = xpos + dx[dir];
		int ny = ypos + dy[dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		if (visited[nx][ny]) continue;
		visited[nx][ny] = true;
		cand.push_back(make_pair(nx, ny));
		ret = max(ret, dfs(nx, ny, cand));
		visited[nx][ny] = false;
		cand.pop_back();
	}
	return ret;
}

int getMountShape(int sx, int sy)
{
	int ret = 0;
	vector<pair<int, int>> mountcand;
	for (int shape = 0; shape < 4; shape++) {
		mountcand.clear();
		for (int i = 0; i < 4; i++) {
			int nx = sx + mountShape[shape][i][0];
			int ny = sy + mountShape[shape][i][1];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) break;
			mountcand.push_back(make_pair(nx, ny));
		}
		if (mountcand.size() < 4) continue;
		ret = max(ret, getSum(mountcand));
	}
	return ret;
}

int solution()
{
	int ret = 0;
	vector<pair<int, int>> cand;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			cand.clear();
			ret = max({ ret, dfs(r, c, cand), getMountShape(r,c) });
		}
	}
	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N >> M;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			cin >> board[r][c];
		}
	}
	cout << solution() << endl;
}