백준14500 - 테트로미노

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

14500번: 테트로미노

처음에 만만하게 봐서 bfs를 이용하여 풀었는데 생각해보니 ㅗ모양은 bfs로 찾을 수 없어서 애먹었던 문제다. 또한 4개짜리 조각을 찾으면 찾았던 길을 거슬러와서 다시 미방문처리도 해야된다. 여러모로 생각할 것이 많았던 좋은 문제다.

 

#include <iostream>
#include <stack>
#include <string.h>
#include <algorithm>
#define MAX 501
using namespace std;

class Point {
public:
	int x, y, z, k; //x와 y는 위치, z는 지금까지 먹은 칸의 갯수, k는 점수
	Point(int x, int y, int z, int k) {
		this->x = x;
		this->y = y;
		this->z = z; 
		this->k = k;
	}
};

int mat[MAX][MAX]; //좌표 정보
bool visit[MAX][MAX]; //방문 여부
int N, M;

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

int ans = -1; //답

void func(int x, int y, int z, int k) {
	visit[x][y] = true;
	if (z == 4) { //조각 4개를 먹으면
		ans = max(ans, k); //답으로 큰 값을 찾는다.
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (1 <= nx && nx <= N && 1 <= ny && ny <= M && !visit[nx][ny]) { //범위 안에 있고 방문하지 않은 조각이면
			func(nx, ny, z + 1, k + mat[nx][ny]); //그 조각으로 탐색
			visit[nx][ny] = false; //탐색이 종료되고 미방문처리
		}
	}
} 

//ㅗ모양
void anofunc(int i, int j) {
	if (1 <= i - 1 && i + 1 <= N && 1 <= j - 1 && j - 1 <= M) { //ㅗ모양
		ans = max(mat[i - 1][j] + mat[i][j] + mat[i + 1][j] + mat[i][j - 1], ans);
	}
	if (1 <= i - 1 && i + 1 <= N && 1 <= j + 1 && j + 1 <= M) { //ㅜ모양
		ans = max(mat[i - 1][j] + mat[i][j] + mat[i + 1][j] + mat[i][j + 1], ans);
	}
	if (1 <= i + 1 && i + 1 <= N && 1 <= j - 1 && j + 1 <= M) { //ㅏ모양
		ans = max(mat[i + 1][j] + mat[i][j] + mat[i][j - 1] + mat[i][j + 1], ans);
	}
	if (1 <= i - 1 && i - 1 <= N && 1 <= j - 1 && j + 1 <= M) { //ㅓ모양
		ans = max(mat[i - 1][j] + mat[i][j] + mat[i][j - 1] + mat[i][j + 1], ans);
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> mat[i][j];
		}
	}

	//각각의 조각마다 탐색
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			memset(visit, false, sizeof(bool) * MAX * MAX);
			func(i, j, 1, mat[i][j]);
			anofunc(i, j);
		}
	}

	cout << ans;
}