백준 14500번 _테트로미노

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

14500번: 테트로미노

풀이방법

 이 문제는 그냥 하드코딩해도 된다. board를 돌리고, 대칭시켜 돌리고 하면 8개 종류의 boad모양이 나오는데, 그걸 그냥 하나하나 모양에 맞춰봐도 된다.

 

 하지만, 잘 생각해보면 테트로미노의 넓이 값이 4로 고정되어 있다는것에 대해 생각해보면, 길이가 4인 bfs라고도 생각해볼수있다. 그러므로 bfs로 풀면 간단히 풀린다.

 그런데 나는 시간이 충분한점과 처음에 생각없이 dfs로 짜서, 그냥 dfs가 만들수 없는 모양인 ㅓ,ㅜ,ㅏ,ㅗ 모양은 따로 구현해서 덧붙였다.

---

전체코드

(하드 코딩)

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

using namespace std;

//map을 회전, 대칭시켜 8개를 만든다
//시계방향순
int map1[501][501];	//n, m
int map2[501][501];	//m, n
int map3[501][501];	//n, m
int map4[501][501];	//m,n
//대칭시킨맵, 시계방향순
int map5[501][501];	//n, m
int map6[501][501];	//m, n
int map7[501][501];	//n, m
int map8[501][501];	//m, n
int n, m;

//map 1 3 5 7 n, m
//2 4 6 8 m, n

void reverse()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			map5[i][(m-1)-j] = map1[i][j];
		}
	}
}

void rotatemap90(int select)
{
	if (select == 1 || select == 3)
		for (int j = 0; j < m; j++)
		{
			for (int i = n - 1; i >= 0; i--)
			{
				if (select == 1)
				{
					map2[j][-i + (n - 1)] = map1[i][j];
					map6[j][-i + (n - 1)] = map5[i][j];
				}
				else if (select == 3)
				{
					map4[j][-i + (n - 1)] = map3[i][j];
					map8[j][-i + (n - 1)] = map7[i][j];
				}
			}
		}

	else
		for (int j = 0; j < n; j++)
		{
			for (int i = m - 1; i >= 0; i--)
			{
				if (select == 2)
				{
					map3[j][-i + (m - 1)] = map2[i][j];
					map7[j][-i + (m - 1)] = map6[i][j];
				}
			}
		}

}

//----모양, 이 모양은 reverse된 map들은 계산할 필요없다
//네모모양은 한가지 맵만 계산해도 됨
//map 1 3 5 7 n, m
//2 4 6 8 m, n
int solution()
{
	int maxValue = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			// ---모앙
			if (j + 3 <= m - 1)
			{
				maxValue = max(maxValue, map1[i][j] + map1[i][j + 1] + map1[i][j + 2] + map1[i][j + 3]);
				maxValue = max(maxValue, map3[i][j] + map3[i][j + 1] + map3[i][j + 2] + map3[i][j + 3]);
			}
			//네모모양
			if (i+1 <= n-1 && j+1 <=m-1)
			{
				maxValue = max(maxValue, map1[i][j] + map1[i][j + 1] + map1[i + 1][j] + map1[i + 1][j + 1]);
			}
			//ㄴ모양 , 번개모양은 겹치므로 같이 ㅎ
			if (i + 2 <= n - 1 && j + 1 <= m - 1)
			{
				//ㄴ
				maxValue = max(maxValue, map1[i][j] + map1[i + 1][j] + map1[i + 2][j] + map1[i + 2][j+1]);
				maxValue = max(maxValue, map3[i][j] + map3[i + 1][j] + map3[i + 2][j] + map3[i + 2][j + 1]);
				maxValue = max(maxValue, map5[i][j] + map5[i + 1][j] + map5[i + 2][j] + map5[i + 2][j + 1]);
				maxValue = max(maxValue, map7[i][j] + map7[i + 1][j] + map7[i + 2][j] + map7[i + 2][j + 1]);

				//번개
				maxValue = max(maxValue, map1[i][j] + map1[i + 1][j] + map1[i + 1][j + 1] + map1[i + 2][j + 1]);
				maxValue = max(maxValue, map3[i][j] + map3[i + 1][j] + map3[i + 1][j + 1] + map3[i + 2][j + 1]);
				maxValue = max(maxValue, map5[i][j] + map5[i + 1][j] + map5[i + 1][j + 1] + map5[i + 2][j + 1]);
				maxValue = max(maxValue, map7[i][j] + map7[i + 1][j] + map7[i + 1][j + 1] + map7[i + 2][j + 1]);
			}
			//ㅜ모양, reverse는 돌릴필요없다
			if (i + 1 <= n - 1 && j + 2 <= m - 1)
			{
				maxValue = max(maxValue, map1[i][j] + map1[i][j + 1] + map1[i][j + 2] + map1[i+1][j + 1]);
				maxValue = max(maxValue, map3[i][j] + map3[i][j + 1] + map3[i][j + 2] + map3[i +1][j + 1]);
			}

		}
	}

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//----모양
			if (j + 3 <= n - 1)
			{
				maxValue = max(maxValue, map2[i][j] + map2[i][j + 1] + map2[i][j + 2] + map2[i][j + 3]);
				maxValue = max(maxValue, map4[i][j] + map4[i][j + 1] + map4[i][j + 2] + map4[i][j + 3]);
			}
			//네모모양은 여기서 돌릴 필요없음
			
			//ㄴ모양
			if (i + 2 <= m - 1 && j + 1 <= n - 1)
			{
				maxValue = max(maxValue, map2[i][j] + map2[i + 1][j] + map2[i + 2][j] + map2[i + 2][j + 1]);
				maxValue = max(maxValue, map4[i][j] + map4[i + 1][j] + map4[i + 2][j] + map4[i + 2][j + 1]);
				maxValue = max(maxValue, map6[i][j] + map6[i + 1][j] + map6[i + 2][j] + map6[i + 2][j + 1]);
				maxValue = max(maxValue, map8[i][j] + map8[i + 1][j] + map8[i + 2][j] + map8[i + 2][j + 1]);

				//번개
				maxValue = max(maxValue, map2[i][j] + map2[i + 1][j] + map2[i + 1][j + 1] + map2[i + 2][j + 1]);
				maxValue = max(maxValue, map4[i][j] + map4[i + 1][j] + map4[i + 1][j + 1] + map4[i + 2][j + 1]);
				maxValue = max(maxValue, map6[i][j] + map6[i + 1][j] + map6[i + 1][j + 1] + map6[i + 2][j + 1]);
				maxValue = max(maxValue, map8[i][j] + map8[i + 1][j] + map8[i + 1][j + 1] + map8[i + 2][j + 1]);
			}
			//ㅜ모양, reverse는 돌릴필요없다
			if (i + 1 <= m - 1 && j + 2 <= n - 1)
			{
				maxValue = max(maxValue, map2[i][j] + map2[i][j + 1] + map2[i][j + 2] + map2[i + 1][j + 1]);
				maxValue = max(maxValue, map4[i][j] + map4[i][j + 1] + map4[i][j + 2] + map4[i + 1][j + 1]);
			}
		}
	}

	return maxValue;
}


int main()
{
	cin >> n >> m;

	//original map 입력
	int value;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> value;
			map1[i][j] = value;
		}
	}
	//original map을 회전시켜 2,3,4 를 구한다 시계방향순임
	reverse();
	for (int i = 1; i <= 4; i++)
		rotatemap90(i);

	cout <<solution();
	return 0;
}

 

(dfs + ㅓ,ㅜ,ㅏ,ㅗ 모양 추가)

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

using namespace std;

int N, M;
int board[502][502];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };


void Input()
{
	cin >> N >> M;
	int value;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> value;
			board[i][j] = value;
		}
	}
}

bool inRange(int y, int x)
{
	if (y >= 0 && x >= 0 && y < N && x < M)
		return true;
	return false;
}

bool visited[502][502];
int dfs(int y, int x, int sum, int cnt)
{
	//탈출조건
	if (cnt == 4)
	{
		return sum + board[y][x];
	}

	sum += board[y][x];

	int ret = 0;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (inRange(ny, nx) == false || visited[ny][nx] == true)
			continue;

		visited[ny][nx] = true;
		ret = max(ret, dfs(ny, nx, sum, cnt + 1));
		visited[ny][nx] = false;
	}
	return ret;
}

//dfs로 안되는 ㅜ는 모두비교 
int compareLastFigure()
{
	int maxValue = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			//ㅏ
			if (i + 2 <= N - 1 && j + 1 <= M - 1)
			{
				maxValue = max(maxValue, board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j + 1]);
			}

			//ㅜ
			if (i + 1 <= N - 1 && j + 2 <= M - 1)
			{
				maxValue = max(maxValue, board[i][j] + board[i + 1][j + 1] + board[i][j + 1] + board[i][j + 2]);
			}

			//ㅓ
			if (i + 1 <= N - 1 && j + 1 <= M - 1 && i - 1 >= 0)
			{
				maxValue = max(maxValue, board[i][j] + board[i - 1][j + 1] + board[i][j + 1] + board[i + 1][j + 1]);
			}

			//ㅗ
			if (i + 1 <= N - 1 && j + 2 <= M - 1 && i - 1 >= 0)
			{
				maxValue = max(maxValue, board[i][j] + board[i - 1][j + 1] + board[i][j + 1] + board[i][j + 2]);
			}
		}
	}
	return maxValue;
}

void solve()
{
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			visited[i][j] = true;
			ans = max(ans, dfs(i, j, 0, 1));
			visited[i][j] = false;
		}
	}
	ans = max(compareLastFigure(), ans);
	cout << ans;
}

int main()
{
	Input();
	solve();
	return 0;
}

---

후기

저번에 풀었었던 문제인데 bfs로 풀려다 뭐가 계속 꼬이길래 dfs+ ㅓ,ㅜ,ㅏ,ㅗ 모양 추가의 꼴로 풀었다.