[C] Backjoon 14500 테트로미노

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

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

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

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

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;
}