백준 14500_테트로미노(C++)

 

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

14500번: 테트로미노

[문제 풀이]

DFS와 시뮬레이션을 이용하여 문제를 풀었습니다.

 

이번 문제는 2차원 배열에서

 

5가지 형태로 이루어진 부분 배열의 최대값을 찾는 문제였습니다. ㅗ의 형태를 제외한 나머지의 경우는 깊이가 3인 DFS의 모든 형태를 말합니다. 이를 찾기 위해서 DFS를 이용하여 4가지 형태의 합을 구했고 ㅗ 형태는 따로 구현해 주었습니다.

[코드]

#include<iostream>
#include<algorithm>

using namespace std;

int N, M;
int result = 0;

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

int map[500][500];
int visit[500][500];

void dfs(int, int, int, int);
void shape(int, int);

int max(int a, int b) { return (a >= b) ? a : b; }

int main() {

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

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visit[i][j] = 1;
			dfs(i, j, map[i][j], 1);
			shape(i, j);
			visit[i][j] = 0;
		}
	}


	printf("%d\n", result);

}

void shape(int x, int y) {

	int temp = 0;
	//ㅗ
	if (x - 1 >= 0 && y + 2 < M) {
		temp = map[x][y] + map[x][y+ 1] + map[x][y + 2] + map[x - 1][y + 1];
		result = max(result, temp);
	}
	//ㅏ
	if (x + 2 < N && y + 1 < M) {
		temp = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y + 1];
		result = max(result, temp);
	}
	//ㅜ
	if (x + 1 < N && y + 2 < M) {
		temp = map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x + 1][y + 1];
		result = max(result, temp);
	}
	//ㅓ
	if (x + 2 < N && y - 1 >= 0) {
		temp = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y - 1];
		result = max(result, temp);
	}


}

void dfs(int x, int y, int value,int cnt) {

	if (cnt == 4) {
		result = max(result, value);
		return;
	}

	for (int i = 0; i < 4; i++) {

		int nx = x + dx[i];
		int ny = y + dy[i];

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

		visit[nx][ny] = 1;
		dfs(nx, ny, value + map[nx][ny], cnt + 1);
		visit[nx][ny] = 0;

	}

}