문제 설명

1과 0으로 채워진 표(board)가 있습니다. 표 1칸은 1x1의 정사각으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각을 찾아 넓이를 return 하는 solution 함수를 완성해주세요.

예를들어

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

으로 이루어진 표가 있다면 가장 큰 정사각형은

0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0

가 되며 넓이는 9가 되므로 9를 반환해주면 됩니다.

제한사항

• 표는 2차원 배열로 주어집니다.

• 표의 행 크기 : 1000 이하의 자연수

• 표의 열 크기 : 1000 이하의 자연수

• 표의 값은 0 또는 1로만 이루어져 있습니다.

입출력 예

[[0, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [0, 0, 1, 0]] => 9

[[0, 0, 1, 1], [1, 1, 1, 1]] => 4

Solution

문제 해결의 접근법을 찾지 못해 오랜시간 고민한 문제로써 결과적으로 다른사람들의 접근법 및 풀이법을 참고하여 풀이하였다.

DP 접근법이라고는 하지만 DP를 알아야만 해결할 수 있는 문제는 아니다. 실제로 처음 여러 접근법에 대해 고민했을 때 비슷한 접근법을 고민했었다. (아쉽게도 구현단계까진 구체화 하지 못했지만)

접근법은 좌측, 상측, 좌상(왼쪽 대각선 위)측의 상태에 따라 현재 위치가 갖는 가장 큰 정사각형 크기(상태)를 표시하는 것 이다. 즉, 어떤 위치에서의 가장 큰 정사각형을 알기 위해서는 앞서 표시해 둔 좌측, 상측, 좌상측이 어떤 상태냐에 따라 결정된다. 라는 점을 파악해야 한다.

- 현재 위치가 사각형에 해당(1)되고, 좌, 상, 좌상 모두 같은 값(k)를 갖는다면 현재 위치에서의 가장 큰 정사각형의 넓이는 [k + 1]이다.

- 현재 위치가 사각형에 해당(1)되고 좌, 상, 좌상이 서로 다른 값을 갖는다면 현재 위치에서의 가장 큰 정사각형의 넓이는 [좌, 상, 좌상의 최소값 + 1]이다

텍스트로는 잘 이해가 가지 않을 수 있다. 아래 그림을 보자.

그림에서 알 수 있듯 좌, 상, 좌상 위치에 따라 현재 위치의 상태(가장 큰 정사각형)를 표시하고 다음 위치에서 표시한 상태값들을 이용한다.

Code

솔루션에서 언급한 접근법을 코드에 적용하면 위와 같다.

최초에 주어진 board와 board의 사각형 여부에 따라 표시할 dp배열을 생성한다.

생성한 dp 배열은 board의 크기보다 행,열 모두 1씩 더 크게 주었는데, 이는 i=0 또는 j=0일 때의 배열 계산을 편리하게 하기 위함이다.

board의 각 요소를 탐색하면서 값이 1 일 때 dp의 좌, 상, 좌상의 최소값 + 1을 표시한다 (현재 위치가 현재 시점에 속하는 가장 큰 정사각형의 크기)

최종적으로 board 배열의 모든 요소들을 탐색하고나면 dp 배열에서 가장 큰 값이 바로 가장 큰 정사각형의 크기이다.

몇줄 평

• 프로그래머스 레벨2에서 dp문제가 나올줄은 상상도 못했다.

• 사실 접근법만 알고있다면 저엉말 쉬운문제이다.

• 2차원 배열에서 주변 요소들을 이용하여 dp 배열에 상태값을 저장하는 패턴을 배웠다.

참고 및 출처