[백준 - 1028] 다이아몬드 광산

0과 1로 된 격자에서 가장 큰 마름모 테두리를 찾아야 한다. 구현에서는 후보 크기를 1부터 늘려 가면서, 이전 크기의 윗부분이 가능했던 위치만 다음 후보로 확장했다.

새 크기의 다이아몬드는 위쪽 두 변과 아래쪽 두 변이 모두 1이어야 한다. 그래서 후보 꼭짓점마다 대각선 방향의 경계를 직접 확인하고, 네 변을 통과하면 현재 최대 크기를 갱신했다.

처음부터 모든 크기와 모든 꼭짓점을 완전히 다시 검사하지 않고, dp[y][x] == size - 1인 위치만 다음 크기로 키웠다. 작은 다이아몬드가 성립한 자리에서만 큰 다이아몬드를 시도한 것이 이 구현의 중심이다.

문제: 1028 다이아몬드 광산 · 코드: GitHub에서 보기