[백준 C++] 14500번: 테트로미노

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

 

브루트 포스를 이용하여 해결한 문제. 우선 n ,m값을 받아오고 점수를 저장하는 a[i]값을 받아온다.

 

각 블럭별로 점수를 계산하여 가장 큰값을 출력해야 하는데 우선 블럭의 갯수부터 생각해보았다.

 

0000블럭은 가로 세로로 두가지 가능하고

 

00

00 블럭은 한가지 경우만 가능하다.

 

0

000 블럭은 회전 방향에 따라 총 4가지 가능하고 뒤집은 다음 다시 또 4가지 총 8가지의 경우의 수가 가능하다.

 

00

  00 블럭은 회전 방향에 따라 총 2가지 가능하고 뒤집은 다음 다시 또 2가지 총 4가지의 경우의 수가 가능하다.

 

  0

000 블럭은 회전 방향에 따라 총 4가지 가능하다.

 

따라서 모두 합치면 총 19가지의 경우에 블럭의 모양이 가능하고 이를 이용하여 배열을 생각해보았다.

bool 형태의 삼차원 배열을 만들어서 맨 앞에는 블럭의 종류 그뒤에는 n축, m축을 각각 만들어서 1일때

합을 계산하고 0일때는 계산하지 않는 형태로 코드를 짜보았다.

 

이런식으로 출력되도록 코드를 짠뒤 점검하였고 그뒤에 하나씩 넣으며 점수를 계산하였다.

 

코드를 짜다보니 엄청 비효율적이라 생각이 들었고 하나하나 검사하기엔 너무 많다는 생각이 들었다. 

 

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int n, m, ans = 0;
int a[501][501] = { 0, };
int visited[500][500];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
void DFS(int y, int x, int d, int sum);
void T(int y, int x);
 
 
 
int main(int argc, char* argv[])
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
 
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			DFS(i, j, 1, 0);
			T(i, j);
		}
	}
 
	cout << ans;
 
	return 0;
}
void DFS(int y, int x, int d, int sum) {
	sum += a[y][x];
	visited[y][x] = 1;
	if (d == 4) {
		if (sum > ans)
			ans = sum;
		visited[y][x] = 0;
		return;
	}
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
			if (!visited[ny][nx])
				DFS(ny, nx, d + 1, sum);
		}
	}
	visited[y][x] = 0;
}
 
void T(int y, int x) {
	int sum, dir, ny, nx;
	for (int i = 0; i < 4; i++) {
		sum = a[y][x];
		for (dir = 0; dir < 4; dir++) {
			if (dir == i)
				continue;
			ny = y + dy[dir];
			nx = x + dx[dir];
			if (ny >= 0 && ny < n && nx >= 0 && nx < m)
				sum += a[ny][nx];
		}
		if (sum > ans)
			ans = sum;
	}
}

다음에 풀자..