백준/14500번/테트로미노/골드4

July 13, 2023

카테고리: CodingTest

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

문제 설명

Site: Baekjoon
Number: 14500
Category: Bruteforce, DFS
Rank: Gold 4

테트리스 블럭들을 테트로미노라고 한다.

최소 넓이와 높이가 4보다 크거나 같은 2차원 배열에서 한 종류의 테트로미노를 놓았을때 배열에 있는 숫자들의 합의 최대를 구하는 문제.

필자는 모든 좌표를 지나가며(Bruteforce) 1x4 크기에 들어가는 테트로미노, 2x3, 3x2, 4x1로 나누어 가시성을 높였다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int ans, N, M;

int arr[500][500];

void OnebyFour(const int& x, const int& y)
{
	if (y + 3 >= M)
		return;

	int total = 0;

	for (int j = y; j < y + 4; j++)
		total += arr[x][j];

	// 가로 테트로미노
	ans = max(ans, total);
}

void TwobyThree(const int& x, const int& y)
{
	if (x + 1 >= N || y + 2 >= M)
		return;

	int total = 0;

	for(int i = x; i < x+2; i++)
	{
		for(int j = y; j < y+3; j++)
		{
			total += arr[i][j];
		}
	}

	//네모 테트로미노
	ans = max(max(ans, total - arr[x][y+2] - arr[x+1][y+2]), total - arr[x][y] - arr[x+1][y]);

	//L or J 테트로미노
	ans = max(max(ans, total - arr[x + 1][y + 1] - arr[x + 1][y + 2]), total - arr[x + 1][y] - arr[x + 1][y + 1]);
	ans = max(max(ans, total - arr[x][y] - arr[x][y + 1]), total - arr[x][y + 1] - arr[x][y + 2]);

	//Z or S 테트로미노
	ans = max(max(ans, total - arr[x][y] - arr[x + 1][y + 2]), total - arr[x + 1][y] - arr[x][y + 2]);

	//T 테트로미노
	ans = max(max(ans, total - arr[x][y] - arr[x][y + 2]), total - arr[x + 1][y] - arr[x + 1][y + 2]);
}

void ThreebyTwo(const int& x, const int& y)
{
	if (x + 2 >= N || y + 1 >= M)
		return;

	int total = 0;

	for (int i = x; i < x + 3; i++)
	{
		for (int j = y; j < y + 2; j++)
		{
			total += arr[i][j];
		}
	}

	//중복하여 네모를 체크하지 않는다

	//L or J 테트로미노
	ans = max(max(ans, total - arr[x][y] - arr[x + 1][y]), total - arr[x][y + 1] - arr[x + 1][y + 1]);
	ans = max(max(ans, total - arr[x + 1][y] - arr[x + 2][y]), total - arr[x + 1][y + 1] - arr[x + 2][y + 1]);

	//Z or S 테트로미노
	ans = max(max(ans, total - arr[x][y] - arr[x + 2][y + 1]), total - arr[x][y + 1] - arr[x + 2][y]);

	//T 테트로미노
	ans = max(max(ans, total - arr[x][y + 1] - arr[x + 2][y + 1]), total - arr[x][y] - arr[x + 2][y]);
}

void FourbyOne(const int& x, const int& y)
{
	if (x + 3 >= N)
		return;

	int total = 0;

	for (int i = x; i < x + 4; i++)
		total += arr[i][y];

	//세로 테트로미노
	ans = max(ans, total);
}

int main()
{
	ios_base::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 >> arr[i][j];

  //모든 좌표를 지나며 크기별 들어갈 수 있는 테트로미노 확인
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			OnebyFour(i, j);
			TwobyThree(i, j);
			ThreebyTwo(i, j);
			FourbyOne(i, j);
		}
	}

	cout << ans;

	return 0;
}

백준14500

하지만 문제 해결 후 다른 사람의 풀이를 보니 더욱 쉬운 방법이 있었다.

ㅜ자 모양 테트로미노를 제외한 나머지 테트로미노는 한 좌표에서 dfs를 통해 나타낼 수 있는 형태이다.

그러므로 주어진 좌표에서 갈 수 있는 모든 dfs를 통해 똑같이 문제를 해결할 수 있지만, 중복된 테트로미노 확인을 자주하기 때문에 연산 시간이 늘어난다는 단점이 있다.

백준에서 찾은 한 유저는 ㅜ자 모양 테트로미노를 검사할때 한 좌표에서 십자를 가져와 각 상하좌우를 하나 지우고 판별하는 방식을 사용하였다.

//백준 Canplane이라는 유저의 코드
#include <bits/stdc++.h>

int N,M,A[502][502];

int dy[]={-1,0,0,1},dx[]={0,-1,1,0};
int dfs(int y,int x,int d)
{
	if (d==4)	return 0;

	int ret=0,a=A[y][x],i=4,ny,nx;
	A[y][x]=0;
	while (i--)
		if (A[ny=y+dy[i]][nx=x+dx[i]])
			ret=std::max(ret,dfs(ny,nx,d+1));
	return (A[y][x]=a)+ret;
}
int T(int y,int x)
{
	int sum=A[y][x],ret=0,i=4;
	while (i--)	sum+=A[y+dy[i]][x+dx[i]];
	i = 4;
	while (i--)	ret=std::max(ret,sum-A[y+dy[i]][x+dx[i]]);
	return ret;
}
int main()
{
	int ans=0,y,x;
	scanf("%d %d",&N,&M);
	for (y=1;y<=N;y++)
		for (x=1;x<=M;x++)
			scanf("%d",&A[y][x]);

	for (y=1;y<=N;y++)
		for (x=1;x<=M;x++)
			ans=std::max(std::max(ans,dfs(y,x,0)),T(y,x));
	printf("%d",ans);
}

평생하는 개발 공부

문제 설명