[BOJ] 14500번_테트로미노_브루트포스 (C++)

[문제]

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

크기가 N*N인 종이 위에 테트로미노 하나를 놓을 때, 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하는 문제이다.

테트로미노란 아래 조건을 만족하는 도형이다.

• 1*1 크기의 정사각형을 4개 이어 붙인 도형이다.
• 정사각형은 서로 겹치면 안된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 연결되어 있는 것이 아니다.

나는 처음에 그냥 dfs로 풀면 되는거 아닌가? 라는 생각을 했었는데, 이 문제의 핵심인 ㅓ,ㅜ,ㅏ,ㅗ 모양인 테트로미노는 dfs를 사용해서 합을 구할 수 없다는 것을 간과해서 엄청 해멨다.

[사용 알고리즘]

브루트포스 알고리즘, dfs(깊이 우선 탐색)

[풀이 핵심]

• 편의상으로 테트로미노에 쓰여 있는 수들의 합을 테트로미노의 합이라고 한다.
• 이 문제는 위에서 언급했던 T자 모양의 테트로미노의 합을 구하는 과정이 핵심이다.
• 먼저 dfs를 사용해서 T자 모양이 아닌 테트로미노의 합을 구한다. 깊이가 4가 될때까지 dfs를 돌고 깊이가 4가되면 테트로미노의 합의 최대값을 갱신해준다.
• 그리고 현재 노드를 가운데로 생각하고 상하좌우 방향 중 3방향을 탐색하며 T자 모양의 테트로미노의 합을 구하고 최대값을 갱신해준다. T자 모양은 총 4가지(ㅓ,ㅜ,ㅏ,ㅗ)가 존재하므로 4가지 경우의 테트로미노의 합을 구해야한다.

[코드]

//boj14500_테트로미노_브루트포스 알고리즘

#include<iostream>

using namespace std;

int graph[501][501];
bool visited[501][501];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int N, M;

int result;

void DFS(int x, int y, int cnt, int sum) {
	visited[x][y] = true;
	cnt++;

	if (cnt == 4) {
		result = max(result, sum);
		visited[x][y] = false;
		return;
	}

	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y]) {
			DFS(next_x, next_y, cnt, sum + graph[next_x][next_y]);
		}
	}
	visited[x][y] = false;
}

void T_shape(int x, int y) {
	int T_sum;

	if (x - 1 >= 0 && x + 1 < N && y - 1 >= 0) {
		T_sum = graph[x][y] + graph[x - 1][y] + graph[x + 1][y] + graph[x][y - 1];
		result = max(result, T_sum);
	}
	if (x - 1 >= 0 && y - 1 >= 0 && y + 1 < M) {
		T_sum = graph[x][y] + graph[x - 1][y] + graph[x][y - 1] + graph[x][y + 1];
		result = max(result, T_sum);
	}
	if (x - 1 >= 0 && x + 1 < N && y + 1 < M) {
		T_sum = graph[x][y] + graph[x - 1][y] + graph[x + 1][y] + graph[x][y + 1];
		result = max(result, T_sum);
	}
	if (x + 1 < N && y - 1 >= 0 && y + 1 < M) {
		T_sum = graph[x][y] + graph[x + 1][y] + graph[x][y - 1] + graph[x][y + 1];
		result = max(result, T_sum);
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			DFS(i, j, 0, graph[i][j]);
			T_shape(i, j);
		}
	}

	cout << result;

	return 0;
}