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

안녕하세요 오늘 풀어볼 문제는 테트로미노 입니다.

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

 

테트로미노는 문제는 기본 DFS에서 몇 가지 더 고려해줘야 하는 부분이 있습니다.

1. T자형 테트로미노

2. 가지치기

---

1. T자형 테트로미노

T자형 테트로미노는 T처럼 생긴 테트로미노에요.

 

다른 모양의 테트로미노는 DFS로 검사할 수 있지만 T자형은 그럴 수 없습니다.

왜일까요?

 

각 테트로미노의 탐색 방향을 표시해봤어요.

다른 모양의 테트로미노들은 모두 한 붓 그리기가 가능합니다.

즉, 하나의 분기를 하나의 경우로 취급하는 DFS로 탐색하기 적절하다는 뜻이지요.

이건 대칭이나 회전을 시켜도 동일합니다.

 

그런데 T자형 테트로미노는 2번 이상 분기하지 않으면 탐색이 불가능합니다.

그래서 각 좌표에서 T자형 테트로미노만 따로 탐색하는 처리를 해줘야 합니다.

 

다행히 대칭, 회전을 포함해도 ㅜ/ㅗ/ㅏ/ㅓ 4가지 경우 밖에 없기 때문에 하드코딩을 통해 처리를 해줄 수 있습니다.

void check_t_shape(int x, int y) {
	int center = paper[x][y];
	int sum;

	// ㅗ
	if (x >= 0 && x + 1 < N && y - 1 >= 0 && y + 1 < M) {
		sum = center + paper[x + 1][y] + paper[x][y - 1] + paper[x][y + 1];
		mx_sum = max(mx_sum, sum);
	}
	// ㅜ
	if (x - 1 >= 0 && x < N && y - 1 >= 0 && y + 1 < M) {
		sum = center + paper[x - 1][y] + paper[x][y - 1] + paper[x][y + 1];
		mx_sum = max(mx_sum, sum);
	}
	// ㅏ
	if (x - 1 >= 0 && x + 1 < N && y + 1 < M) {
		sum = center + paper[x - 1][y] + paper[x + 1][y] + paper[x][y + 1];
		mx_sum = max(mx_sum, sum);
	}
	// ㅓ
	if (x - 1 >= 0 && x + 1 < N && y - 1 >= 0) {
		sum = center + paper[x - 1][y] + paper[x + 1][y] + paper[x][y - 1];
		mx_sum = max(mx_sum, sum);
	}
}

---

2. 가지치기

테트로미노 문제에서는 이미 방문한 좌표를 다시 방문하는 경우가 얼마든지 있을 수 있어요,

그래서 매 좌표마다 방문 배열을 초기화 해줘야 하는데요.

이런 처리는 물론 (CPU가...) 감당할 수 없는 중복된 검사를 초래합니다.

 

대신 저는 각 DFS에서 더 적은 재귀 호출을 하도록 가지치기(Pruning)을 적용해줬어요.

 

가지치기의 기준은 '누적 점수 + 남은 깊이 * 종이 위에 있는 최고 점수 <= 누적 최고점' 입니다.

if (score + (4 - depth) * mx_val <= mx_sum)return;

---

위 두 조건을 제외한다면 테트로미노는 아주 간단한 문제인 거 같아요.

대신 처음에 두 조건을 떠올리는 게 관건이겠네요.

 

아래는 코드 전문입니다.

#include <iostream>
#include <cstring>
using namespace std;

int N, M;
int paper[501][501];
bool visited[501][501];
int mx_val = 0, mx_sum = 0;

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

void check_t_shape(int x, int y) {
	int center = paper[x][y];
	int sum;

	// ㅗ
	if (x >= 0 && x + 1 < N && y - 1 >= 0 && y + 1 < M) {
		sum = center + paper[x + 1][y] + paper[x][y - 1] + paper[x][y + 1];
		mx_sum = max(mx_sum, sum);
	}
	// ㅜ
	if (x - 1 >= 0 && x < N && y - 1 >= 0 && y + 1 < M) {
		sum = center + paper[x - 1][y] + paper[x][y - 1] + paper[x][y + 1];
		mx_sum = max(mx_sum, sum);
	}
	// ㅏ
	if (x - 1 >= 0 && x + 1 < N && y + 1 < M) {
		sum = center + paper[x - 1][y] + paper[x + 1][y] + paper[x][y + 1];
		mx_sum = max(mx_sum, sum);
	}
	// ㅓ
	if (x - 1 >= 0 && x + 1 < N && y - 1 >= 0) {
		sum = center + paper[x - 1][y] + paper[x + 1][y] + paper[x][y - 1];
		mx_sum = max(mx_sum, sum);
	}
}

void dfs(int x, int y, int score, int depth) {
	score += paper[x][y];
	visited[x][y] = 1;
	depth += 1;

	if (depth == 4) {
		mx_sum = max(score, mx_sum);
		return;
	}

	if (score + (4 - depth) * mx_val <= mx_sum)return;

	for (int dir = 0; dir < 4; dir++) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];

		if (nx < 0 || nx >= N || ny < 0 || ny >= M)continue;
		if (visited[nx][ny])continue;

		dfs(nx, ny, score, depth);
	}
}

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

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> paper[i][j];
			mx_val = max(paper[i][j], mx_val);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			check_t_shape(i, j);
			for (int k = 0; k < N; k++)
				memset(visited[k], 0, sizeof(visited[k]));

			dfs(i, j, 0, 0);
			
		}
	}

	cout << mx_sum;
}