[DP] Maximal Square

1로 구성된 사각형의 최대 크기를 구한다

 

다음과 같은 원리를 적용해보았다

크기와 모양이 같은 Matrix를 만든 후 , dp로 각각 순회한다

1을 발견했을 때 왼쪽, 위쪽, 좌상단의 값이 모두 1이면 정사각형이 구성된다

이 경우 길이가 2인 정사각형이 만들어지므로 해당 node를 2로 변경한다

 

 

일단 index가 되는 매트릭스를 구성하는데 input matrix에 행렬을 하나씩 더한 값으로 구성한다

 

왜냐하면 1.1 위치가 1일때 node를 1로 순회해주려면 기준값을 주는 것이 편하기 때문이다

 

이후 루프를 도는데, 하나씩 돌면서 값이 1인 노드를 만나는 경우, 왼쪽,위쪽,좌상단쪽 중 가장 작은 값에 1을 더해 업데이트 해준다

그게 아니라면 노드는 0으로 설정한다

이렇게 업데이트 된 값은 정사각형을 구성할 수 있는 변의 최대길이가 될 것이기 때문에 그것이 max보다 크다면 max를 업데이트 해준다

최종적으로 정사각형의 크기를 리턴하므로, max의 제곱을 리턴하면 된다.

약간 새로운 유형의 dp라서 헷갈렸다