(javascript) 알고리즘 문제 - 가장 큰 정사각형 찾기 ( 완벽이해, 설명 )

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다.

표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요.

(단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

예를 들어,

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

 

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

 

• 제한사항
  • 표(board)는 2차원 배열로 주어집니다.
  • 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
  • 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
  • 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

 

• 입출력 예 #1

board	answer
[[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

 

• 입출력 예 #2

0	0	1	1
1	1	1	1

로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

 

---

이 문제를 풀기 앞서..

수 많은 검색 끝에 이 문제를 풀기 위해선 Dynamic Programming(동적 계획법)을 사용해야 한단 것을 알았습니다.

DP에 대해 간략히 설명하자면

Dynamic Programming(동적 계획법)
기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것.

DP를 사용하기 위해선 다음 2가지 조건을 만족해야한다.
1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)

더 자세한 내용을 설명하기엔 길어지기에 자세한 내용은 아래 포스팅한 게시글을 읽어보시면 이해되실 겁니다.

2022.09.19 - [코딩테스트] - [알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법

 

---

문제를 이해하기 위해

이 문제를 이해하는데 상당히 많은 시간이 걸렸어서 그림으로 쉽게 이해를 돕고자 합니다.

아래의 코드를 보시면서 보신다면 훨 씬 이해가 빠르실 겁니다.

 

1. 만약 행 또는 열이 1이면 정사각형의 넓이는 1
2. 루프를 돌며 만약 자신의 위치(현재 인덱스)의 값이 1이상일 경우 왼쪽상단(↖︎), 위쪽(↑), 왼쪽(←)의 최솟값을 구한 후 자신의 위치에 최솟값 + 1을 할당
3. i 가 0이 아닌 1부터 시작하는 이유는 좌측값, 상단값, 대각선값을 확인하여 현재값을 변경하기 때문입니다.
4. 1행 1열 부터 시작하여 한 열에서 하나의 행을 다 돌고 다음 열로 넘어갑니다. 
5. 순환이 끝나면 배열의 가장 큰 값이 현재 배열의 가장 큰 정사각형의 값이 됩니다.
6. 사각형의 넓이는 한 변의 길이 * 한 변의 길이로 정사각형은 변의 길이가 같기 때문에 한변의 길이 2제곱을 해줍니다.

 

1열 순환 예시

현재위치의 값을 제외한  좌측값, 상단값, 대각선값을 비교하여 가장 작은 값 + 1로 현재값을 변경합니다.

 

• [1, 1] 1행 1열

가장 작은 값이 대각선의 값 0이 므로 현재 값은 0+1 인 1이 됩니다.

 

• [2, 1] 2행 1열

가장 작은 값이 좌측값, 상단값, 대각선값 모두 1 이므로 현재 값은 1+1 인 2가 됩니다.

 

• [3, 1] 3행 1열

가장 작은 값이 상단값, 대각선값인 1 이므로 현재 값은 1+1 인 2가 됩니다.

 

2열 순환 예시

• [1, 2] 1행 2열

가장 작은 값이 좌측값, 상단값, 대각선값 모두 1 이므로 현재 값은 1+1 인 2가 됩니다.

 

• [2, 2] 2행 2열

가장 작은 값이 대각선값 1 이므로 현재 값은 1+1 인 2가 됩니다.

 

• [3, 2] 3행 2열

가장 작은 값이 좌측값, 상단값, 대각선값 모두 2 이므로 현재 값은 2+1 인 3이 됩니다.

 

3열 순환 예시

• [1, 3] 1행 3열

board [i] [j] > 0 으로 0보다 커야하지만 크지 않기 때문에 2행으로 넘어갑니다.

 

• [2, 3] 2행 3열

가장 작은 값이 좌측값 0 이므로 현재 값은 0+1 인 1이 됩니다.

 

• [3, 3] 3행 3열

board [i] [j] > 0 으로 0보다 커야하지만 크지 않기 때문에 넘어가며 i < board.length , i < board[0].length 의 길이인 4 전 까지이기 때문에

for 구문은 종료됩니다.

 

전체 순환 그림

한 눈에 보기 편하도록 위 순환 열들을 합친 그림도 첨부합니다.

그림이 많이 조잡하네요 ..

---

solution.js

마지막으로 코드 첨부합니다.

위 풀이 방법들을 보시면서 코드를 보시면 이해하기 편하실겁니다.

혹시나 이해 안되는 부분있으면 댓글 남겨주세요 (●'◡'●)

function solution(board) {
    let answer = 0;
    const row = board.length;
    const column = board[0].length;
  
    if (row <= 1 || column <= 1) return 1; 
  
    for (let i = 1; i < row; i++) { // 1행부터 시작
      for (let j = 1; j < column; j++) { // 1열부터 시작
        if (board[i][j] > 0) { 
          const up = board[i - 1][j]; 
          const left = board[i][j - 1];
          const cross = board[i - 1][j - 1];
          const minNum = Math.min(up, left, cross); // 3개의 값 중 가장 작은 값

          board[i][j] = minNum + 1; 

          console.log(board[i][j]);

          answer = Math.max(answer, board[i][j]); 
        }
      }
    }
  
    return answer **2; 
  }