백준 14500 (테트로미노)

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

14500번: 테트로미노

풀이

DFS를 사용하여 풀이하면 되는 문제이다.

1. 최대 입력값은 500이기 때문에 배열의 크기는 500으로 할당

2. ㅗ 도형을 제외한 나머지 도형은 위, 아래, 우측, 좌측 으로 이동하며 DFS를 돌리면 도형이 나온다.

EX ) 우측, 우측, 우측, 우측 -> " ---- " 과 같이 예제에서 주어지는 도형 중 " ㅗ " 자 도형을 제외한 모든 경우의 수는 위, 아래, 왼쪽, 오른쪽 방향으로 움직이면서 경우의 수 탐색

3. 2번에서 ㅗ 도형을 제외한 모든 도형의 경우의 수에 알맞는 합을 구하여 max 값을 갱신했으니 나머지 ㅗ 도형에 대한 값을 구하면 된다. ㅗ 자 도형은 각 좌표를 설정하여 대칭, 회전 한 모든 경우의 수를 3차원 배열에 담아둔 뒤 DFS 수행

  + "ㅗ" 도형 좌표 구하는 방법

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
int map[500][500];
int visit[500][500];
int my, mx;
int maxx = 0;

// ㅗ 자 모양
int dcheck[4][4][2] = {
	{
		0,0,
		1,0,
		1,-1,
		1,1
	}, 
	{
		0,0,
		0,1,
		0,2,
		1,1
	},
	{
		0,0,
		1,0,
		1,-1,
		2,0
	},
	{
		0,0,
		1,0,
		2,0,
		1,1,
	}
};

// 상하좌우
int check[5][2] = {
	0,0,
	1, 0,
	-1, 0,
	0, 1,
	0, -1
};

// ㅗ 모형을 제외한 모형의 모든 경우의 수 탐색
void dfs_b(int level, int y, int x, int sum){
	if (level == 4){
		if (sum > maxx) maxx = sum;
		return;
	}
	for (int i = 0; i < 5; ++i){
		int dy = y + check[i][0];
		int dx = x + check[i][1];
		if (dy >= 0 && dx >= 0 && dy < my && dx < mx && visit[dy][dx] == 0){
			visit[dy][dx] = 1;
			dfs_b(level + 1, dy, dx, sum + map[dy][dx]);
			visit[dy][dx] = 0;
		}
	}
}

// ㅗ 모형에 대한 경우의 수 탐색
void dfs_a(int level, int y, int x, int sum, int idx){
	if (level == 4){
		if (sum > maxx) maxx = sum;
		return;
	}

	for (int i = 0; i < 4; ++i){
		int dy = y + dcheck[idx][i][0];
		int dx = x + dcheck[idx][i][1];
		if (dy >= 0 && dx >= 0 && dy < my && dx < mx && visit[dy][dx] == 0){
			visit[dy][dx] = 1;
			dfs_a(level + 1, y, x, sum + map[dy][dx], idx);
			visit[dy][dx] = 0;
		}
	}
}

int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> my >> mx;
	for (int i = 0; i < my; ++i){
		for (int j = 0; j < mx; ++j){
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < my; ++i){
		for (int j = 0; j < mx; ++j){
			dfs_b(0, i, j, 0);
			for (int idx = 0; idx < 4; ++idx){
				dfs_a(0, i, j, 0, idx);
			}
		}
	}


	printf("%d", maxx);
}