백준 14500 테트로미노 c++ (dfs)

풀이

dfs 문제이다. 

테트로미노들은 모두 4칸으로 이루어져있고, 사실상 dfs depth를 4로 했을 때 갈 수 있는 최대값이 도형들의 모양이 되는 것을 확인할 수 있다.

따라서 dfs를 depth 4로 해서 최대값을 구현하면 된다. 

배열에 있는 모든 점에 대해서 수행을 해야한다.

그리고 ㅗ 모양에 대해서는 완전 탐색으로 구현하면 된다

 

for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			visited[i][j] = 1;
			dfs(j, i, 1, arr[i][j]);
			visited[i][j] = 0;
			check(j, i);
		}
	}

 

메인함수의 일부분이다. 이 함수를 보면, dfs를 통해서 depth 4인 탐색을 수행한다.

check는 매뉴얼하게 ㅗ 모양의 도형이 들어가는지, 들어간다면 각각 회전하고 대칭시켰을 때의 값을 확인해주는 함수이다.

 

간단했지만 생각하기가 어려운 문제였다. 완전탐색으로도 풀 수 있지만 시간이 올릴 것 같다.

 

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

int N, M;
int arr[501][501];
int visited[501][501];
int ans;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, 1 };

void check(int x, int y) {
	if (x + 2 < M && y + 1 < N) {
		ans = max(ans, arr[y][x] + arr[y][x + 1] + arr[y][x + 2] + arr[y + 1][x + 1]);
	}
	if (y + 2 < N && x + 1 < M) {
		ans = max(ans, arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y + 1][x + 1]);
	}
	if (y - 1 >= 0 && y + 1 < N && x + 1 < M) {
		ans = max(ans, arr[y][x] + arr[y - 1][x + 1] + arr[y][x + 1] + arr[y + 1][x + 1]);
	}
	if (y - 1 >= 0 && x + 2 < M) {
		ans = max(ans, arr[y][x] + arr[y - 1][x + 1] + arr[y][x + 1]+arr[y][x + 2]);
	}
	return;
}
void dfs(int x, int y, int cnt, int sum) {
	if (cnt == 4) {
		ans = max(ans, sum);
		return;
	}
	for (int i = 0;i < 4;i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= M || ny >= N) {
			continue;
		}
		if (visited[ny][nx] == 1) {
			continue;
		}
		visited[ny][nx] = 1;
		dfs(nx, ny, cnt + 1, sum + arr[ny][nx]);
		visited[ny][nx] = 0;
	}

}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N >> M;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			visited[i][j] = 1;
			dfs(j, i, 1, arr[i][j]);
			visited[i][j] = 0;
			check(j, i);
		}
	}
	cout << ans << endl;
	return 0;
}