[C] Algorithm : Backjoon 14500 테트로미노

Baekjoon Problem 14500 is tetromino. Please check the details and pictures of the problem in Baekjonn. For uncomplicated algorithmic problems, it is possible to code the problem right away, but it is possible to reduce trial and error by analyzing the problem and thinking about which functions and elements to solve the problem and organizing it.

백준 14500번 문제는 테트리미노이다. 문제에 대한 내용과 그림 등은 백준에서 직접 확인하길 바란다. 복잡하지 않은 알고리즘 문제에서는 바로 코딩을 해도 되지만, 문제를 분석하고 어떤 함수와 요소들을 활용하여 문제를 해결할지 고민하고 정리하는 것이 시행착오를 줄일 수 있다.

Analysis of the problem requirements is as follows.

1. When placing tetromino on paper, calculate the sum of the hidden values
2. Calculate the maximum value by checking all the number of tetromino cases

문제 요구 사항을 분석하면 아래와 같다.

1. 종이 위에 테트로미노를 위치시켰을 때, 가려지는 값의 합을 계산
2. 테트로미노 경우의 수를 모두 확인하여 최대값을 계산

The detailed requirements and analysis of the problem are as follows.

1. Tetrimino is any shape that can come out by joining 4 squares together
2. Tetrimino can be rotated and symmetrical when attached to paper
3. The number of all cases satisfying 1 and 2 matches the number of all cases created by moving 4 times in the array DFS.
4. In 3, the bump shape of tetrimino is omitted, so the bump shape is implemented as a separate function.

문제 상세 요건 및 분석사항은 아래와 같다.

1. 테트리미노는 4개의 정사각형을 이어붙여서 나올 수 있는 모든 모양
2. 테트리미노는 종이에 부착시 회전 및 대칭이 가능
3. 1,2를 만족시키는 모든 경우의 수는 배열 DFS에서 4번 이동하여 만드는 모든 경우의 수와 일치한다.
4. 3 으로는 요철 모양의 테트리미노가 누락되므로, 요철모양은 따로 함수형태로 구현한다.

#include <stdio.h>

int mat[501][501];
int visit[501][501];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int g_sum;


void bump(int x, int y, int N, int M) {
	for (int k = 0; k < 4; k++) {
		int s1 = mat[x][y];
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < N && ny< M && nx >= 0 && ny >= 0) s1 += mat[nx][ny];
		}
		if (x + dx[k] < N && y + dy[k] < M && x + dx[k] >= 0 && y + dy[k] >= 0) s1 -= mat[x + dx[k]][y + dy[k]];
		if (s1 > g_sum) g_sum = s1;
	}
}

void DFS(int x, int y, int N, int M, int dep, int sum) {
	if (dep == 0) {
		visit[x][y] = 1;
	}
	if (dep == 4) {
		if (g_sum < sum) g_sum = sum;
	}
	else {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= N || ny >= M || nx < 0 || ny < 0) continue;
			if (visit[nx][ny] == 1) continue;
			visit[nx][ny] = 1;
			DFS(nx, ny, N, M, dep + 1, sum + mat[x][y]);
			visit[nx][ny] = 0;
		}
	}
}

int main() {

	int N, M;
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &mat[i][j]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {			
			DFS(i, j, N, M, 0, 0);
			visit[i][j] = 0;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			bump(i, j, N, M);
		}
	}
	printf("%d", g_sum);
	return 0;
}