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

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

 

전형적인 DFS문제이다. 

위 입력과 같이 인풋이 주어질 때 테트리미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력하는 문제이다.

 

map 을 방문하면서 한 위치를 고정으로 dfs를 4번 돌면 테트리미노가 완성된다. 

근데 그중 凸모양(?) 테르리미노는 dfs로 구현이 안되므로 cnt==1일 때 조건을 만들어서 따로 계산한다. 

 

이와 좀 유사한 문제로는 PuyoPuyo(뿌요뿌요)가 있었던 것으로 기억한다. 

 

dfs를 돌면서 어떤 도형을 만드는 형태의 문제는 자주 나오는 문제이므로 한 번 풀어보고 감을 잡는 것이 좋다. 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <vector>

int N, M;
int map[555][555];
bool visit[555][555];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int ans = 0;
void dfs(int y, int x, int sum,int cnt) {
	if (cnt == 4) {
		ans = sum > ans ? sum : ans;
		return;
	}
	if (cnt == 1) {
		int a, b, c, d;
		a = map[y][x + 1] + map[y][x - 1] + map[y][x] + map[y - 1][x];
		b = map[y][x + 1] + map[y][x - 1] + map[y][x] + map[y + 1][x];
		c = map[y][x + 1] + map[y+1][x] + map[y][x] + map[y - 1][x];
		d = map[y][x - 1] + map[y + 1][x] + map[y][x] + map[y - 1][x];
		ans = a > ans ? a : ans;
		ans = b > ans ? b : ans;
		ans = c > ans ? c : ans;
		ans = d > ans ? d : ans;
	}

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny<1 || nx<1 || ny>N || nx>M) continue;
		if (visit[ny][nx]) continue;
		visit[ny][nx] = true;
		dfs(ny, nx, sum + map[ny][nx], cnt + 1);
		visit[ny][nx] = false;
	}

}
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) for (int j = 1; j <=M; j++) scanf("%d", &map[i][j]);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			visit[i][j] = true;
			dfs(i, j, map[i][j],1);
			visit[i][j] = false;
		}
	}
	printf("%d", ans);
}