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

 dfs를 좀 더 점검할 수 있었던 문제이다. 이번 동계학기 삼성 알고리즘 사전 문제에도 비슷한 문제가 나왔었다.

여기서 핵심은 4번의 이동으로 ㅗ ㅏ ㅓ ㅜ 모양을 제외하곤 전부 방문이 가능하므로 카운트하며 돌아가는 백트래킹이다.

 

1. 각 자리에서 dfs하며 지금까지 카운트가 4가 되면 백트래킹

2. dfs 인자에 지금까지 돌며 더한 값을 저장할 값이 필요함

3. 그런데 위의 모양은 조금 노가다를 해야함

4. 나의 경우 cnt 가 3일 경우 방향에 따라 값을 구하도록 했음

 

시간이 살짝 마음에 들지 않지만 보통 이정도 걸리는 것 같음

 

#include <iostream>
#define MAX 500

using namespace std;
int N, M;
int Max = -1;
int board[MAX][MAX];
bool visited[MAX][MAX];

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

bool boundery(int x, int y) {
	if (x < N && x > -1 && y < M && y > -1)
		return true;
	else
		return false;
}

void dfs(int hereX, int hereY, int cnt, int sum, int orix, int oriy) {
	sum += board[hereX][hereY];
	if (cnt == 3) {
		if (hereX == orix) {
			if (oriy > hereY && boundery(hereX - 1, hereY + 1)) 
				if (Max < sum + board[hereX - 1][hereY + 1])
					Max = sum + board[hereX - 1][hereY + 1];

			if (oriy > hereY && boundery(hereX + 1, hereY + 1))
				if (Max < sum + board[hereX + 1][hereY + 1])
					Max = sum + board[hereX + 1][hereY + 1];
			
			if (oriy < hereY && boundery(hereX - 1, hereY - 1)) 
				if (Max < sum + board[hereX - 1][hereY - 1])
					Max = sum + board[hereX - 1][hereY - 1];

			if (oriy < hereY && boundery(hereX + 1, hereY - 1))
				if (Max < sum + board[hereX + 1][hereY - 1])
					Max = sum + board[hereX + 1][hereY - 1];
		}

		if (hereY == oriy) {
			if (orix > hereX && boundery(hereX + 1, hereY - 1))
				if (Max < sum + board[hereX + 1][hereY - 1])
					Max = sum + board[hereX + 1][hereY - 1];

			if (orix > hereX && boundery(hereX + 1, hereY + 1))
				if (Max < sum + board[hereX + 1][hereY + 1])
					Max = sum + board[hereX + 1][hereY + 1];

			if (orix < hereX && boundery(hereX - 1, hereY + 1))
				if (Max < sum + board[hereX - 1][hereY + 1])
					Max = sum + board[hereX - 1][hereY + 1];

			if (orix < hereX && boundery(hereX - 1, hereY - 1))
				if (Max < sum + board[hereX - 1][hereY - 1])
					Max = sum + board[hereX - 1][hereY - 1];
		}

	}

	if (cnt == 4) {
		if (Max < sum) 
			Max = sum;		
		// cout << sum << " : " << hereX << " " << hereY << endl;
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nextX = hereX + dx[i];
		int nextY = hereY + dy[i];

		if (nextX < N && nextX > -1 && nextY < M && nextY > -1 && visited[nextX][nextY] == false) {
			visited[nextX][nextY] = true;
			dfs(nextX, nextY, cnt + 1, sum, orix, oriy);
			visited[nextX][nextY] = false;
		}
	}
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			visited[i][j] = false;
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = true;
			dfs(i, j, 1, 0, i, j);
			visited[i][j] = false;
		}
	}

	cout << Max << '\n';
}