백준 1028번 다이아몬드 광산 C++

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

 

dp[행][열][방향] 3차원 dp배열을 만든다. 방향은 0, 1, 2, 3 순서로 왼쪽 위, 오른쪽 위, 오른쪽 아래, 왼쪽 아래이다.

dp[행][열][방향] 에 들어가는 수는 (행, 열) 에서 [방향] 쪽으로 이어지는 1의 개수이다.

 

배열을 위에서 아래로 순회하면서 왼쪽 위, 오른쪽 위 즉 dp[행][열][0], dp[행][열][1] 을 그 전 좌표의 값 + 1로 채워주고

아래에서 위로 순회하면서 오른쪽 아래, 왼쪽 아래 즉 dp[행][열][2], dp[행][열][3] 을 그 전 좌표의 값 + 1로 채워주었다.

 

다시 배열을 순회하면서 아래로 뻗어지는 두 수 중 작은 값을 기준으로 밑으로 내려가서 밑에서 위로 올라가는 수 중 작은 값이 앞에서 구한 값보다 크거나 같으면 다이아몬드를 만들 수 있다. 이 중 가장 큰 다이아몬드를 구했다.

 

각 좌표마다 4방향으로 얼마나 나아갈 수 있는지는 위에서 dp배열에 저장해놓았다.

그림으로 표현하면

아래로 내려가는 두 경우 중 작은 값을 기준으로 다이아몬드를 만들 수 있는 적절한 좌표를 구한다.

 

이런 방식으로 만들 수 있는 다이아몬드 중 가장 큰 다이아몬드를 구한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

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

	int r, c;
	int max_DIA = 0;
	cin >> r >> c;
	vector<vector<int>> board(r, vector<int>(c));
	vector<vector<vector<int>>> dp(r, vector<vector<int>>(c, vector<int>(4, 0)));
	for (int i = 0; i < r; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < c; j++) {
			board[i][j] = str[j] - '0';
		}
	}

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int row = i;
			int revRow = r - i - 1;
			if (board[row][j]) {
				if (row <= 0 || j <= 0) dp[row][j][0] = 1;
				else dp[row][j][0] = dp[row - 1][j - 1][0] + 1;

				if (row <= 0 || j >= c - 1) dp[row][j][1] = 1;
				else dp[row][j][1] = dp[row - 1][j + 1][1] + 1;
			}
			if (board[revRow][j]) {
				if (revRow >= r - 1 || j >= c - 1) dp[revRow][j][2] = 1;
				else dp[revRow][j][2] = dp[revRow + 1][j + 1][2] + 1;

				if (revRow >= r - 1 || j <= 0) dp[revRow][j][3] = 1;
				else dp[revRow][j][3] = dp[revRow + 1][j - 1][3] + 1;
			}
		}
	}

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int down = min(dp[i][j][2], dp[i][j][3]);
			if (max_DIA >= down) continue;
			for (int k = down; k >= 1; k--) {
				int downRow = 2 * (k - 1) + i;
				if (downRow >= r) continue;
				int up = min(dp[downRow][j][0], dp[downRow][j][1]);
				if (up >= k) {
					max_DIA = max(max_DIA, k);
					break;
				}
			}
		}
	}

	cout << max_DIA;
};