백준 14500 테트로미노 삼성 SW 역량 테스트 기출 문제 c++

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

14500번: 테트로미노

문제 이해 후 구상하는데만 20분 구현에는 두시간이 걸렸다.

 

첫 구상때는 경우의수를 전부 나눠보려고 했는데 그렇게하면 20가지가 넘는 경우의 수가 나오게돼서 하루를 전부 구현해도 안나올 경우의 수였다.

 

그래서 다시한번 생각을 해보니 ㅗ 모양을 제외한 나머지 케이스는 dfs를 이용했을때 깊이가 3인 것들이었다.

가로 세로의 길이가 최대 500x500 이기에 행렬의 원소 한개씩 브루트포스를 해서 구해도 문제가 없다고 생각해 백트래킹을 이용한 브루트포스를 구현했다.

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

using namespace std;
int result = 0;
int v[501][501];
int check[501][501];
int n,m;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

void dfs(int x,int y,int cnt,int sum)
{
	if(cnt == 4) {
		if(result < sum) {
			result = sum;
		}
		return;
	}
	
	for(int i=0; i<4; i++) {
		int nx = dx[i] + x;
		int ny = dy[i] + y;
		
		if(nx < 1 || ny < 1 || nx > n || ny > m || check[nx][ny])	continue;
		check[nx][ny] = 1;
		dfs(nx,ny,cnt+1,sum+v[nx][ny]);
		check[nx][ny] = 0;
	}
	
	if(x-1>=1 && y-1>=1 && x+1<=n) {
		result = max(result,(v[x-1][y] + v[x][y-1] + v[x][y] + v[x+1][y]));
	}
	if(x-1>=1 && y+1<=m && x+1<=n) {
		result = max(result,(v[x-1][y] + v[x][y+1] + v[x][y] + v[x+1][y]));
	}
	if(y-1>=1 && x+1<=n && y+1<=m) {
		result = max(result,(v[x][y] + v[x+1][y] + v[x+1][y+1] + v[x+1][y-1]));
	}
	if(y-1>=1 && x+1<=n && y+1<=m) {
		result = max(result,(v[x][y-1] + v[x][y] + v[x][y+1] + v[x+1][y]));
	}
}


int main(void)
{
	cin >> n >> m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin >> v[i][j];
		}
	}
	
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			check[i][j] = 1;
			dfs(i,j,1,v[i][j]);
			check[i][j] = 0;
		}
	}
	cout << result;
	return 0;
}

 

ㅗ의 경우는 ㅗ,ㅜ,ㅏ,ㅓ 네가지 경우를 따로 구현해주면 된다.