프로그래머스 Lv.2: 가장 큰 정사각형 찾기

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

이 문제는 풀이를 보고 푼 문제로, Dynamic programming 으로 풀어야 한다.

다이나믹 프로그래밍은 사실 단어 뜻과는 다르게 "기록하는 프로그래밍"이다.
이 문제를 통해서 "기록하며 나아가는 것"이 뭔지 확실히 배운 것 같다.

방법은 이렇다.

먼저 기존의 board에 왼쪽과 위쪽을 0으로 채운 새로운 배열을 만든다.
새로 만든 배열을 반복문을 돌면서 (1,1 부터 시작)

만약 arr(i,j) 를 x 라고 하고, x 가 1일 경우,

1 0
1 1(x)

라면, x를 나머지 3개의 최솟값 + 1 로 채운다. 저 예시에서 x를 1 로 채우게 된다. 1의 뜻은 길이가 1인 정사각형이라는 뜻이다.

만약에

1 1
1 1(x)

이라면?

x 는 2 가 된다. 어라? 1이 네개라서 길이가 2인 정사각형으로 기록되었다.

이런 식으로 숫자를 채우면서 내려가면 정사각형의 길이가 기록되게 된다.

여기서 가장 큰 숫자를 제곱하여 return 하면 끝.

function solution(board) {
    if (board.length === 1) return 1;
    if (board[0].length === 1) return 1;
    
    let row = board.length;
    let col = board[0].length;
    var answer = 0;
    let arr = Array(row + 1).fill(0)
              .map(e => Array(col + 1).fill(0));
    
    // 1. board의 맨 왼쪽과 위에 0 으로 채운 새로운 배열을 만든다.
    for (let i = 0; i < row; i++){
        for (let j = 0; j < col; j++){
            arr[i+1][j+1] = board[i][j]
        } 
    }
    
    for (let i = 1; i <= row; i++) {
        for (let j = 1; j <= col; j++){
            if (arr[i][j] !== 0){
                arr[i][j] = Math.min(arr[i-1][j-1], 
                                     arr[i][j-1], 
                                     arr[i-1][j]) + 1
                answer = Math.max(answer, arr[i][j])
            }
        }
    }
    return answer**2;
}