[JS] 2Level / 연습문제 / 무인도 여행

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12905?language=javascript

프로그래머스

 

문제 풀이 방법

저장된 값을 사용하는 DP 알고리즘을 이용했다.

표를 순회하며 해당 칸의 숫자가 1이면 좌, 좌 대각선 위, 위 의 숫자 중 가장 작은 수에 1을 더해 재할당 해준다.

이렇게 재할당된 수를 다시 이용하며 DP 알고리즘을 적용한다.

그리고 answer의 값과 해당 칸의 수를 비교한 뒤 큰 값을 answer에 할당해준 다음 반복문이 끝나면 정사각형의 넓이를 반환해야 하므로 answer ** 2 (제곱) 한 뒤 답으로 반환해준다.

 

코드

const solution = (board) => {
    let answer = 0;
    
    if(board.length <= 1 || board[0].length <= 1) return 1;
    
    for(let i=1; i<board.length; i++){
        for(let j=1; j<board[0].length; j++){
            if(board[i][j] === 1){
                board[i][j] = Math.min(board[i-1][j-1], board[i][j-1], board[i-1][j]) + 1;
                answer = Math.max(answer, board[i][j]);
            }
        }
    }
    return answer**2;
}