백준 14500 [C++]

www.acmicpc.net/problem/14500

14500번: 테트로미노

1. 문제풀이 방법

 

- 테트리스에 너무 익숙한 탓일까요....?

 

- 문제조건에서 대칭을 시켜도 된다는 조건을 빼먹고...이건 뭐 아이디어가 안떠올라서 모든 좌표탐색을 했으나

 

- 대칭을 안넣었으니...당연히 틀릴 수 밖에 없었습니다....

 

- 문제 조건을 다시 파악하고 보니 DFS 깊이 4짜리에 해당하는 모든 좌표가 테트로미노로 표현이 된다는 것을

  알아내었습니다....

 

- 하지만 ㅗ ㅏ ㅜ ㅓ 는 DFS로 표현이 불가능 합니다 (집합느낌으로 보면 테트로미노 > 4짜리 DFS?) 이런느낌?

 

- 그래서 그건 따로 직접 좌표를 설정해 구해주었습니다.

 

 

 

 

2. 주의사항

 

- 문제를 똑바로 파악하자!!!!

 

 

3. 나의코드

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

int N, M;
int tetro[501][501];
int maxvalue = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool visit[501][501];
int depth = 0;
int tmpsum;

void dfs(int x, int y) {
	if (depth == 4) {
		if (tmpsum > maxvalue) maxvalue = tmpsum;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int x2 = x + dx[i];
		int y2 = y + dy[i];
		if (x2 >= 0 && x2 < N &&y2 >= 0 && y2 < M && visit[x2][y2]==false) {
			visit[x2][y2] = true;
			depth++;
			tmpsum += tetro[x2][y2];
			dfs(x2, y2);
			tmpsum -= tetro[x2][y2];
			depth--;
			visit[x2][y2] = false;
		}
	}
}

void cantdfs(int x, int y)
{
	int result = 0;
	if (x - 1 >= 0 && y + 2 < M) {// ㅗ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x][y + 2] + tetro[x - 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 1 < N &&y + 2 < M) { // ㅜ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x][y + 2] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 1 < N &&x - 1 >= 0 && y + 1 < M) { // ㅓ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x - 1][y + 1] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 2 < N &&y + 1 < M) {
		result = tetro[x][y] + tetro[x + 1][y] + tetro[x + 2][y] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tetro[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			depth = 1;
			tmpsum = tetro[i][j];
			visit[i][j] = true;
			dfs(i, j);
			visit[i][j] = false;
			cantdfs(i, j);
		}
	}
	cout << maxvalue << "\n";

	return 0;
}