[BOJ]14500번: 테트로미노(c++)

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

14500번: 테트로미노

 

 

방법 1: 이게 최선입니까휴먼...? 방법

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int tetromino(vector<vector<int>> &board, int i, int j)
{
	int v_len = board.size();
	int h_len = board[0].size();

	int ttrm_max = 0;

	// Type A - 가로 세로
	if (i < v_len && j + 3 < h_len)
	{
		int t = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i][j + 3];
		ttrm_max = max(ttrm_max, t);
	}
	if (i + 3 < v_len && j < h_len)
	{
		int t = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 3][j];
		ttrm_max = max(ttrm_max, t);
	}

	// Type B
	if (i + 1 < v_len && j + 1 < h_len)
	{
		int t = board[i][j] + board[i][j + 1] + board[i + 1][j] + board[i + 1][j + 1];
		ttrm_max = max(ttrm_max, t);
	}

	// Type C - 가로 세로
	if (i + 1 < v_len && j + 2 < h_len)
	{
		int t_1 = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j];
		int t_2 = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 2];
		int t_3 = board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2] + board[i][j];
		int t_4 = board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2] + board[i][j + 2];
		ttrm_max = max({ ttrm_max , t_1, t_2, t_3, t_4 });
	}
	if (i + 2 < v_len && j + 1 < h_len)
	{
		int t_1 = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i][j + 1];
		int t_2 = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 2][j + 1];
		int t_3 = board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1] + board[i][j];
		int t_4 = board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1] + board[i + 2][j];
		ttrm_max = max({ ttrm_max , t_1, t_2, t_3, t_4});
	}

	// Type D - 가로 세로
	if (i + 1 < v_len && j + 2 < h_len)
	{
		int t_1 = board[i][j + 1] + board[i + 1][j + 1] + board[i][j] + board[i + 1][j + 2];
		int t_2 = board[i][j + 1] + board[i + 1][j + 1] + board[i + 1][j] + board[i][j + 2];
		ttrm_max = max({ ttrm_max , t_1, t_2 });
	}
	if (i + 2 < v_len && j + 1 < h_len)
	{
		int t_1 = board[i + 1][j] + board[i + 1][j + 1] + board[i][j] + board[i + 2][j + 1];
		int t_2 = board[i + 1][j] + board[i + 1][j + 1] + board[i][j + 1] + board[i + 2][j];
		ttrm_max = max({ ttrm_max , t_1, t_2});
	}

	// Type E - 가로 세로
	if (i + 1 < v_len && j + 2 < h_len)
	{
		int t_1 = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 1];
		int t_2 = board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2] + board[i][j + 1];
		ttrm_max = max({ ttrm_max , t_1, t_2 });
	}
	if (i + 2 < v_len && j + 1 < h_len)
	{
		int t_1 = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j + 1];
		int t_2 = board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1] + board[i + 1][j];
		ttrm_max = max({ ttrm_max , t_1, t_2 });
	}

	return ttrm_max;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N, M;
	cin >> N >> M;

	vector<vector<int>> board(N);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			int tmp;
			cin >> tmp;
			board[i].push_back(tmp);
		}
	}

	// 테트로미노 최대값 구하기
	int ttrm_max = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			// 현재위치에서 가능한 테트로미노의 최대값
			ttrm_max = max(ttrm_max, tetromino(board, i, j));
		}
	}

	cout << ttrm_max;

	return 0;
}

 

방법 2: 위치값 배열을 따로 만드는 방법

#include <iostream>
#include <algorithm>

using namespace std;

// 테트로미노 위치값
int ttrmn[19][3][2] = {
	// Type A - 가로
	{{0,1}, {0,2}, {0,3}},
	// Type A - 세로
	{{1,0}, {2,0}, {3,0}},
	// Type B
	{{0,1}, {1,0}, {1,1}},
	// Type C - 가로
	{{0,1}, {0,2}, {-1,2}},
	{{1,0}, {1,1}, {1,2}},
	{{0,1}, {0,2}, {1,2}},
	{{0,1}, {0,2}, {1,0}},
	// Type C - 세로
	{{1,0}, {2,0}, {0,1}},
	{{1,0}, {2,0}, {2,1}},
	{{0,1}, {1,1}, {2,1}},
	{{0,1}, {-1,1}, {-2,1}},
	// Type D - 가로 
	{{0,1}, {1,1}, {1,2}},
	{{0,1}, {-1,1}, {-1,2}},
	// Type D - 세로
	{{1,0}, {1,1}, {2,1}},
	{{1,0}, {0,1}, {-1,1}},
	// Type E - 가로
	{{0,1}, {0,2}, {1,1}},
	{{0,1}, {0,2}, {-1,1}},
	// Type E - 세로
	{{1,0}, {2,0}, {1,1}},
	{{1,0}, {2,0}, {1,-1}},
};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	const int MAX = 500;
	int board[MAX][MAX];

	// 입력
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}

	// 테트로미노 최대값 구하기
	int t_max = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			// 현재위치에서 가능한 19가지 유형 테트로미노의 최대값
			for (int k = 0; k < 19; k++)
			{
				int t = board[i][j];
				bool possible = true;
				for (int l = 0; l < 3; l++)
				{
					// 위치값
					int y = i + ttrmn[k][l][0];
					int x = j + ttrmn[k][l][1];
				
					if (0 <= y && y < N && 0 <= x && x < M)
					{
						t += board[y][x];
					}
					else
					{
						possible = false;
						break;
					}
				}

				// 테트로미노 완성가능하면 최대값 교환
				if (possible)
				{
					t_max = max(t_max, t);
				}
			}
		}
	}

	cout << t_max;

	return 0;
}

 

방법 3: ㅗ제외한 모양은 dfs로, ㅗ모양은 따로 체크하기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dr_x[4] = {0, 1, 0, -1};
int dr_y[4] = {1, 0, -1, 0};
int N, M, max_sum;

// ㅗ를 제외한 나머지 도형 체크
void dfs(vector<vector<int>> &nums, vector<vector<bool>> &visit, int x, int y, int sum, int depth)
{
	// 4번째 칸 이동이 끝난 경우
	if (depth == 4)
	{
		max_sum = max(sum, max_sum);
		return;
	}
	// 이동이 불가능한 경우
	if (x < 0 || x >= N || y < 0 || y >= M)
	{
		return;
	}
	// 이미 지나온 칸인 경우
	if (visit[x][y])
	{
		return;
	}

	// 이동가능한 4방향 탐색 후 dfs재귀함수 호출
	visit[x][y] = true;
	for (int i = 0; i < 4; ++i)
	{
		dfs(nums, visit, x + dr_x[i], y + dr_y[i], sum + nums[x][y], depth + 1);
	}
	visit[x][y] = false;
}

// ㅗ모양 도형 체크
void check_t_shape(vector<vector<int>>& nums, int x, int y)
{
	if (x + 2 < N)
	{
		int sum = nums[x][y] + nums[x + 1][y] + nums[x + 2][y];
		if (y - 1 >= 0)
		{
			max_sum = max(sum + nums[x + 1][y - 1], max_sum);
		}
		if (y + 1 < M)
		{
			max_sum = max(sum + nums[x + 1][y + 1], max_sum);
		}
	}

	if (y + 2 < M)
	{
		int sum = nums[x][y] + nums[x][y + 1] + nums[x][y + 2];
		if (x - 1 >= 0)
		{
			max_sum = max(sum + nums[x - 1][y + 1], max_sum);
		}
		if (x + 1 < N)
		{
			max_sum = max(sum + nums[x + 1][y + 1], max_sum);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> N >> M;
	vector<vector<int>> nums(N, vector<int>(M));
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> nums[i][j];
		}
	}

	// 입력받은 배열 탐색하며 테트로미노 합계 구하기
	vector<vector<bool>> visit(N, vector<bool>(M));
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			/*
				ㅗ를 제외한 나머지 도형
				: 해당 위치에서 이동가능한 방향으로 3칸이동하며 합계 구하고 max값 체크
			*/
			dfs(nums, visit, i, j, 0, 0);

			// ㅗ모양 도형 체크
			check_t_shape(nums, i, j);
		}
	}

	// 출력
	cout << max_sum;

	return 0;
}

 

 

유지보수성으로 따지면 방법 3 > 2 > 1 순으로 낫고..

속도는 방법 1 > 2> 3순이다.

 

 

방법 3은 ㅗ모양을 제외하면, 회전/대칭된 각 도형은

사실상 시작위치에서 가능한 4방향으로 뻗어나간 도형이다.

 

따라서 ㅗ도형만 빼고 재귀함수로 처리가능하다. 

이 문제에선 속도가 현저하게 느려지는게 흠이지만,

만약 코테에서 나온다면 방법 3으로 푸는게 제일 코딩시간이 단축되지 않을까..