BOJ 14500 테트로미노 / C++

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

14500번: 테트로미노

백준 온라인저지 14500 테트로미노 문제입니다.

 

아이디어

이 문제는 처음에 생각했던 풀이는 모든 모양의 폴리오미노를 모든 방향인 케이스를 배열에 저장하여 탐색하려 했는데 배열을 만들다보니 이건 아니다 싶을정도로 많이 나왔습니다. 그래서 구글링하여 다른분들의 풀이를 참고 했는데 ㅗ모양을 제외한 나머지의 모양은 depth 3의 dfs로 풀어낼 수 있다는 걸 알았네요... 물론 배열을 모두 저장하여 풀이해도 정답을 받을 수 있다고 합니다. dfs로 풀어내는 풀이가 더 마음에 들어서 시도해보진 않고 아래와 같이 풀이 했습니다.

 

#include <iostream>
#include <vector>
#define MAX 501
using namespace std;

int arr[MAX][MAX];
bool visited[MAX][MAX];
int n, m;
int sol;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1, -1, 0,0 };

class point {
public :
	point(int Y, int X) {
		x = X;
		y = Y;
	}
	int x;
	int y;
};

//폴리오미노는 ㅗ모양을 제외하면 3depth를 가지기 때문에 dfs로 풀 수 있음
void dfs(point p, int sum, int cnt) {
	if (cnt == 3) {
		if (sol < sum)
			sol = sum;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int y = p.y + dy[i];
		int x = p.x + dx[i];
		if (y >= n || y < 0 || x >= m || x < 0) continue;
		if (visited[y][x]) continue;
		visited[y][x] = true;
		dfs(point(y, x), sum + arr[y][x], cnt + 1);
		visited[y][x] = false;
	}
}

//ㅗ모양의 4가지 방향
void parts1(int y, int x)
{
	int sum = arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y + 1][x - 1];
	if (sum > sol) sol = sum;

}

void parts2(int y, int x)
{
	int sum = arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y + 1][x + 1];
	if (sum > sol) sol = sum;
}

void parts3(int y, int x)
{
	int sum = arr[y][x] + arr[y][x + 1] + arr[y][x + 2] + arr[y + 1][x + 1];
	if (sum > sol) sol = sum;
}

void parts4(int y, int x)
{
	int sum = arr[y][x] + arr[y+1][x- 1] + arr[y+1][x] + arr[y + 1][x + 1];
	if (sum > sol) sol = sum;
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
}


void solution() {


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = true;
			dfs(point(i, j), arr[i][j], 0);
			if (j - 1 >= 0 && i + 2 < n) parts1(i, j);
			if (i + 2 < n && j + 1 < m) parts2(i, j);
			if (j + 2 < m && i + 1 < n) parts3(i, j);
			if (j + 1 < m && j - 1 >= 0 && i + 1 < n) parts4(i, j);
			visited[i][j] = false;
		}
	}
	cout << sol;
}

int main(void) {
	input();
	solution();
}