1139. Largest 1-Bordered Square

1139. Largest 1-Bordered Square

https://leetcode.com/problems/largest-1-bordered-square/

문제

풀이

grid[0][0]일 때를 보자.
(0,0)기준으로 width = 3, height = 3 인 것을 알 수 있다. 그 이유는 다 1이기 때문이다.
대각선 화살표가 지나간 부분을 확인한다.

(2, 2)부분에서 width, height을 구한다. 3, 3이므로 (0,0)에 해당 정사각형은 9가 된다.

만약 이렇게 된다면 width = 3, height = 1이기 때문에 정사각형이 만들어 질 수 없다. 이제 그 앞에 대각선인 (1, 1)을 보게 되면 width = 2, height = 2이기에 (0, 0) 정사각형은 4가 된다.

이것을 코드로 나타내면 다음과 같다.

앞에서 설명했을 때 대각선 부분에서 다시 width, height 구하는 과정을 vertical, horizon배열로 대체하였다. 그래서 모든 grid에서 발생할 수 있는 정사각형 중 최대값을 구하는 코드이다.

결과