[스위프트 알고리즘] 프로그래머스: 가장 큰 정사각형 찾기

문제

https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 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를 반환해 주면 됩니다.

풀이

다이나믹 프로그래밍으로 해결합니다. 

 

dp 배열은 초기에는 주어진 배열과 일치하고 dp 배열에는 해당 위치를 기준으로 만들 수 있는 정사각형의 최대 개수를 의미합니다. 정사각형의 개수를 구하기 위해서 다음과 같은 알고리즘으로 개수를 판별합니다.

1. board 배열을 순회하면서 각 위치를 탐색합니다.
   1. 현재 위치의 값이 0이라면 아무것도 하지 않고 건너뜁니다.
   2. 현재 위치의 값이 1이라면 최소 한 개의 정사각형을 만들 수 있습니다.
2. 현재 위치의 값이 1일 때, 만들 수 있는 최대 정사각형을 확인하기 위해서 dp 배열에서 자신의 좌측, 우측, 좌측 대각선 방향의 값을 확인합니다. board 배열을 각 행을 이동하면서 순회하기 때문에 dp 배열의 좌측, 우측, 좌측 대각선에는 해당 위치로부터 만들 수 있는 최대 정사각형의 개수가 저장되어 있습니다.
3. 따라서 현재 위치에서 얻을 수 있는 정사각형의 최대 개수는  좌측, 우측, 좌측 대각선 에 저장된 정사각형의 개수 중 최소값에 1을 더한 개수입니다. 좌측, 우측, 좌측 대각선 방향이 모두 1로 채워져 있어야 정사각형을 만들 수 있기 때문입니다.

코드