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

안녕하세요 평범한 컴공생입니다.

 

백준 14500번 [테트로미노] 문제 알고리즘 포스팅을 해보겠습니다.쉽지 않은 문제였지만 그렇다고 도전하기도 전에 겁을 먹을 문제는 아니었습니다.

 

SW역량테스트 문제입니다. 도전해 볼 가치가 있습니다.

 

골드 5 난이도의 문제입니다

1. 문제 해결 방법 구상하기

 - 4개의 블럭으로 이어진 조각이다? --> 하나의 시작블럭을 잡고 4개의 블럭을 탐색해가면서 더해주자!

 - 이전에 탐색을 하였던 블록이거나, 주어진 격자의 범위를 넘어서는 경우처럼 여러 조건을 걸어주어야 한다.

 - 이 방법대로 한다면 ㅗ 모양과 같은 경우에는 예외의 경우이므로 따로 함수를 만들어 예외처리를 해주어야한다.

케이스 1~4경우로 만들어 ㅜ, ㅓ, ㅏ, ㅗ 의 CASE를 다 탐색해준다.

 - DFS 형식으로 깊이(CNT) 값을 주어 탐색을 해준다.

 

2. 구상한 아이디어를 바탕으로 코딩하기

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int point[500][500];
int maxpoint = -987654321;

bool check[500][500] = { false, };

void search(int r, int c, int sum, int cnt)
{
	check[r][c] = true;
	if (cnt == 4)
	{
		maxpoint = max(maxpoint, sum);
		return;
	}
	if ((r + 1 <= N - 1) && (check[r + 1][c] == false))
	{
		search(r + 1, c, sum+point[r+1][c], cnt+1);
		check[r + 1][c] = false;
	}
	if ((c + 1 <= M - 1) && (check[r][c + 1] == false))
	{
		search(r, c + 1, sum+point[r][c+1], cnt+1);
		check[r][c + 1] = false;
	}
	if ((r - 1 >= 0) && (check[r - 1][c] == false))
	{
		search(r - 1, c, sum+point[r-1][c], cnt+1);
		check[r - 1][c] = false;
	}
	if ((c - 1 >= 0) && (check[r][c - 1] == false))
	{
		search(r, c - 1, sum+point[r][c-1], cnt+1);
		check[r][c - 1] = false;
	}
	check[r][c] = false;
}

void case1(int r, int c)
{
	int shapepoint = point[r][c] + point[r][c + 1] + point[r][c + 2] + point[r + 1][c + 1];
	maxpoint = max(maxpoint, shapepoint);
}

void case2(int r, int c)
{
	int shapepoint = point[r][c] + point[r][c + 1] + point[r-1][c + 1] + point[r + 1][c + 1];
	maxpoint = max(maxpoint, shapepoint);
}

void case3(int r, int c)
{
	int shapepoint = point[r][c] + point[r][c + 1] + point[r-1][c + 1] + point[r][c + 2];
	maxpoint = max(maxpoint, shapepoint);
}

void case4(int r, int c)
{
	int shapepoint = point[r][c] + point[r-1][c] + point[r+1][c] + point[r][c + 1];
	maxpoint = max(maxpoint, shapepoint);
}

void input()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> point[i][j];
}

void solution()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			search(i, j, point[i][j], 1);

	for (int i = 0; i < N - 1; i++)
		for (int j = 0; j < M - 2; j++)
			case1(i,j);

	for (int i = 1; i < N - 1; i++)
		for (int j = 0; j < M - 1; j++)
			case2(i, j);

	for (int i = 1; i < N; i++)
		for (int j = 0; j < M - 2; j++)
			case3(i, j);

	for (int i = 1; i < N - 1; i++)
		for (int j = 0; j < M - 1; j++)
			case4(i, j);
}

int main()
{
	input();
	solution();
	cout << maxpoint << endl;

	return 0;
}

DFS와 좀 더 친숙해질 수 있었던 문제였다. 꽤나 까다로웠지만 범위조건을 잘 제어해주고 예외 케이스들을 잘 처리해주는 작업만 해주면 해결할 수 있었던 문제였다. 이런 SW 역량테스트 문제들을 좀 더 자주 접하고 해결할 수 있는 능력을 갖출 수 있도록 노력해야겠다.

 

/ /문제제기 및 피드백 언제든지 감사히 받겠습니다.