백준 1028 다이아몬드 광산 (c++) : 피너클

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

1028번: 다이아몬드 광산

완전탐색과 다이나믹을 응용해 풀었다.

int r, c;
string map[751];
int up_left[751][751];
int up_right[751][751];
int down_left[751][751];
int down_right[751][751];

사용할 변수다.

up_left는 왼쪽 위로 1이 얼마나 있는지다.

위의 그래프에서 up_left[3][3] = 2다.

그 외 up_right나 down_left도 이름과 맞는 의미를 같는다.

int up_l(int y, int x) {
	if (y < 0 || x < 0 || y >= r || x >= c) return 0;
	if (up_left[y][x] != -1) return up_left[y][x];
	if (map[y][x] == '0') return 0;
	return up_left[y][x] = up_l(y - 1, x - 1) + 1;
}

up_l함수다. y와 x를 전달받으며 up_left[y][x]를 반환한다.

만약 y와 x가 범위에서 벗어나면 그대로 0을 반환하고

이미 up_left[y][x]가 존재하면 up_left[y][x]를 반환한다.

그후 만약 현재 위치가 0이라면 0을 반환하고

아니면 up_left[y][x]에 up_l(y-1, x-1) + 1을 넣으며 반환한다.

이 외에도 up_r, down_l, down_r등 다른 함수도 존재한다.

cin >> r >> c;
for (int i = 0; i < r; i++)
        cin >> map[i];

memset(up_left, -1, sizeof(up_left));
memset(up_right, -1, sizeof(up_right));
memset(down_left, -1, sizeof(down_left));
memset(down_right, -1, sizeof(down_right));

메인함수에서 값을 입력받고 배열들을 -1로 초기화한다.

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        if (map[i][j] == '0') {
            up_left[i][j] = up_right[i][j] = down_left[i][j] = down_right[i][j] = 0;
        }
        else {
            up_left[i][j] = up_l(i, j);
            up_right[i][j] = up_r(i, j);
            down_left[i][j] = down_l(i, j);
            down_right[i][j] = down_r(i, j);
        }
    }
}

그후 모든 map을 훑어보며 

만약 map[i][j]가 0이면 모든 배열을 0으로 하고

아니라면 함수도 모든 배열을 채운다.

int ans = 0;
for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        for (int k = 0; k <= r; k++) {
            int sol = solve(i, j, k) + 1;
            if (sol == -1) break;
            ans = max(ans, sol);
        }
    }
}
cout << ans << '\n';

그후 모든 map을 돌아보며 

sol에 solve(i, j, k) + 1을 넣은뒤 만약 sol이 -1이면 반복문에서 나오고 아니면 ans와 비교해 더 큰수를 넣는다.

그후 ans를 출력하면 된다.

int solve(int y, int x, int size) {
	if (x - size < 0) return -1;
	if (x + size >= c) return -1;
	if (y + 2 * size >= r) return -1;

	if (down_left[y][x] >= size + 1 && down_right[y][x] >= size + 1)
		if (up_left[y + 2 * size][x] >= size + 1 && up_right[y + 2 * size][x] >= size + 1)
			return size;

	return -1;
}

solve함수다. y, x, size를 전달받으며 size는 다이아몬드의 사이즈다. 

size 0:    size 1:    size 2:
                         1
              1         1 1
   1         1 1       1   1
              1         1 1
                         1

위와 같이 사이즈가 올라간다. sol = solve(i, j, k) + 1에서 +1을 한 이유가 이것이다.

이제 만들 다이아몬드의 크기가 map에서 벗어나지 않는지를 확인하고 벗어나면 -1을 반환한다.

그후 다이아몬드를 만들수 있으면 size를 그대로 반환하고 아니면 -1을 반환한다.

다이아몬드의 위와 아래에서 만들수 있는 1의 길이가 size와 같거나 크다면 만들 수 있는 것이다.

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

int r, c;
string map[751];
int up_left[751][751];
int up_right[751][751];
int down_left[751][751];
int down_right[751][751];

int solve(int y, int x, int size) {
	if (x - size < 0) return -1;
	if (x + size >= c) return -1;
	if (y + 2 * size >= r) return -1;

	if (down_left[y][x] >= size + 1 && down_right[y][x] >= size + 1)
		if (up_left[y + 2 * size][x] >= size + 1 && up_right[y + 2 * size][x] >= size + 1)
			return size;

	return -1;
}

int up_l(int y, int x) {
	if (y < 0 || x < 0 || y >= r || x >= c) return 0;
	if (up_left[y][x] != -1) return up_left[y][x];
	if (map[y][x] == '0') return 0;
	return up_left[y][x] = up_l(y - 1, x - 1) + 1;
}
int up_r(int y, int x) {
	if (y < 0 || x < 0 || y >= r || x >= c) return 0;
	if (up_right[y][x] != -1) return up_right[y][x];
	if (map[y][x] == '0') return 0;
	return up_right[y][x] = up_r(y - 1, x + 1) + 1;
}
int down_l(int y, int x) {
	if (y < 0 || x < 0 || y >= r || x >= c) return 0;
	if (down_left[y][x] != -1) return down_left[y][x];
	if (map[y][x] == '0') return 0;
	return down_left[y][x] = down_l(y + 1, x - 1) + 1;
}
int down_r(int y, int x) {
	if (y < 0 || x < 0 || y >= r || x >= c) return 0;
	if (down_right[y][x] != -1) return down_right[y][x];
	if (map[y][x] == '0') return 0;
	return down_right[y][x] = down_r(y + 1, x + 1) + 1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> r >> c;
	for (int i = 0; i < r; i++)
			cin >> map[i];

	memset(up_left, -1, sizeof(up_left));
	memset(up_right, -1, sizeof(up_right));
	memset(down_left, -1, sizeof(down_left));
	memset(down_right, -1, sizeof(down_right));

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] == '0') {
				up_left[i][j] = up_right[i][j] = down_left[i][j] = down_right[i][j] = 0;
			}
			else {
				up_left[i][j] = up_l(i, j);
				up_right[i][j] = up_r(i, j);
				down_left[i][j] = down_l(i, j);
				down_right[i][j] = down_r(i, j);
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			for (int k = 0; k <= r; k++) {
				int sol = solve(i, j, k) + 1;
				if (sol == -1) break;
				ans = max(ans, sol);
			}
		}
	}
	cout << ans << '\n';
}

전체코드다.