[BOJ 1028 // C++] 다이아몬드 광산

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1028번 문제인 다이아몬드 광산이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1028

1028번: 다이아몬드 광산

이 문제는 주어진 2차원 배열에서 가장 큰 "다이아몬드 모양"을 찾는 문제이다.

 

먼저, 다음과 같은 관찰을 하자. (r: 행, c: 열)

 

어떤 크기가 T인 "다이아몬드 모양"이 있다고 생각하자.

1) 이 "다이아몬드 모양"은 가장 위쪽(r값이 작은 쪽)에 하나의 꼭짓점 1이 존재한다.

2) 그 꼭짓점에서 왼쪽 아래방향, 오른쪽 아래방향으로 T-1개의 1이 연속적으로 있어야 한다. 각 방향의 T-1번째 1의 위치를 각각 X, Y라 하자.

3) X에서 오른쪽 아래방향, Y에서 왼쪽 아래방향으로 T-1개의 1이 연속적으로 있어야 한다.

 

위와 같이 생각을 바탕으로, 주어진 2차원 배열에서 각 꼭짓점에서 "왼쪽 아래방향으로 연속한 1의 개수"와 "오른쪽 아래방향으로 연속한 1의 개수"를 미리 계산해둔다면 "가장 위쪽 꼭짓점"으로 하는 다이아몬드의 존재를 빠르게 계산할 수 있게 된다.

 

모든 "다이아몬드 모양"은 "가장 위쪽 꼭짓점"이 존재하므로, 위의 탐색만을 하여도 충분하다.

 

탐색 과정에서, 이미 찾은 크기보다 작거나 같은 다이아몬드는 발견하더라도 답에 영향을 주지 않으므로 찾은 크기보다 큰 다이아몬드만을 탐색해나가면 빠르게 문제를 해결할 수 있다.

 

구현시 배열의 범위를 벗어나지 않게 주의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string field[750];
int diag[750][750][2]; // [i][j][x]: i행 j열 / x = 0: down left, x = 1: down right방향

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int R, C; cin >> R >> C;
	
	for (int i = 0; i < R; i++) {
		cin >> field[i];
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (field[r][c] == '0') continue;
			
			if (diag[r][c][0] == 0) { // down_left방향 탐색
				int rr = r, cc = c;
				int level = 0;

				while (rr < R && cc >= 0) {
					if (field[rr][cc] == '0') break;
					level++;
					rr++; cc--;
				}

				for (int i = 0; i < level; i++) {
					diag[r + i][c - i][0] = level - i;
				}
			}

			if (diag[r][c][1] == 0) { // down_right방향 탐색
				int rr = r, cc = c;
				int level = 0;

				while (rr < R && cc < C) {
					if (field[rr][cc] == '0') break;
					level++;
					rr++; cc++;
				}

				for (int i = 0; i < level; i++) {
					diag[r + i][c + i][1] = level - i;
				}
			}
		}
	}
	
	int ans = 0;

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (field[r][c] == '0') continue;
			int T = min(diag[r][c][0], diag[r][c][1]);
			while (T > ans) {
				if (diag[r + T - 1][c - T + 1][1] >= T && diag[r + T - 1][c + T - 1][0] >= T) 
					ans = T;
				T--;
			}
		}
	}

	cout << ans;
}