[BAEKJOON] 14500번 테트로미노

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

14500번: 테트로미노

문제조건

1. 연결된 4개의 정사각형 블록으로 모양을 만든다.
2. 만들어진 모양을 종이위에 올렸을때, 4개의 숫자의 합의 최댓값은?

접근방법

완전탐색을 위해서 brute force로 접근해봤다.

그래서 전체 map을 돌면서 DFS를 수행할 수 있도록 구현했다.

#include <iostream>
using namespace std;

int n, m, map[501][501], visited[501][501];
int dy[] = { -1, 0 , 1, 0 };
int dx[] = { 0, -1, 0, 1 };
int res;

void dfs(int y, int x, int cnt, int sum) {
	if (cnt == 4) {
		res = max(res, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= n || nx >= m || ny < 0 || nx < 0) continue;
		if (!visited[ny][nx]) {
			visited[ny][nx] = 1;
			dfs(ny, nx, cnt + 1, sum + map[ny][nx]);
			visited[ny][nx] = 0;
		}
		
	}
}


int main(){
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int a;
			cin >> a;
			map[i][j] = a;
		}
	}
	//brute force
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = 1;
			dfs(i, j, 1, map[i][j]);
			visited[i][j] = 0;
		}
	}
	cout << res;
}

역시나,, 그렇게 쉽게 풀릴 문제는 아닌 것 같다.

생각을 해보자. DFS로 탐색을 돌리면, 계속 깊어지기만 하기 때문에

중간에 튀어나온 저 모양을 커버해주지 못한다.

그렇다면 저 모양을 커버하기 위해선 어떻게 해야할까?

중간에 튀어나온 모양을 제외한 모양들은 DFS로 이미 다 커버가 되었으므로, 저 모양에 대한 로직만 추가해주면된다.

어렵게 생각할 필요없이, 다시 Brute Force방식으로 찾아준다.

 

소스코드

#include <iostream>
using namespace std;

int n, m, map[502][502], visited[502][502];
int dy[] = { -1, 0 , 1, 0 };
int dx[] = { 0, -1, 0, 1 };
int res;

void dfs(int y, int x, int cnt, int sum) {
	if (cnt == 4) {
		res = max(res, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny > n || nx > m || ny < 1 || nx < 1) continue;
		if (!visited[ny][nx]) {
			visited[ny][nx] = 1;
			dfs(ny, nx, cnt + 1, sum + map[ny][nx]);
			visited[ny][nx] = 0;
		}
		
	}
}


int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int a;
			cin >> a;
			map[i][j] = a;
		}
	}
	//brute force
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			visited[i][j] = 1;
			dfs(i, j, 1, map[i][j]);
			visited[i][j] = 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int mid = map[i][j];
			int low = 1001;
			for (int k = 0; k < 4; k++) {
				low = min(low, map[i + dy[k]][j + dx[k]]);
				mid += map[i + dy[k]][j + dx[k]];
			}
			res = max(res, mid - low);
		}
	}
	cout << res;
}

우선 십자가 모양을 만들어서 테두리의 4가지중 하나를 빼서 모양을 만드는 방식으로 갔다.

그래서 맵 전체를 돌면서 가운데 값을 하나씩 잡아두고, dy, dx를 이용해서 각 테두리 4개를 방문해서 가장 작은 값을 기록해둔다. 그리고 이전 DFS로 구한 res값과 비교해서 더 크다면 res값을 갱신한다.