[프로그래머스 lev2/JS] 가장 큰 정사각형 찾기

문제 출처

프로그래머스 lev2 - 가장 큰 정사각형 찾기

나의 풀이

1차시도(18.8/100, 효율성 시간초과)

function isRight(max, y, x, matrix, flag) {
  
  while(1) {
    // console.log(max, y, x, flag);
    if(!flag) return max;
    if(x+max-1 > matrix[0].length-1 || y+max-1 > matrix.length-1) return max-1;

    for(let i=0; i<max; i++) {
      for(let j=0; j<max; j++) {
        if(matrix[y+i][x+j] === 0) {
          flag = false;
          break;
        }
      }
    }

    if(flag) max++;
  }
}

function solution(board) {
  let answer = 0;

  for(let i=0; i<board.length; i++) {
    for(let j=0; j<board[0].length; j++) {
      // console.log(i,j);
      answer = Math.max(answer, isRight(1, i, j, board, true))
    }
  }
  return answer*answer;
}

2차시도(정확성 통과, 효율성 실패)

1. 정사각형인지 판별하려면 완전탐색을 해야 할 것 같다.
2. 최소값이 아니라 최대값을 구해야 하므로 넓게 탐색하기보다는 깊게 탐색하는 게 유리할 것 같다. 그래서 dfs/bfs 중에서 dfs를 선택했다.
3. 정확성은 통과해도, 효율성에서 시간초과가 발생하는 것을 보니 동적계획법을 사용해야 할 것 같다.

function isRight(max, y, x, matrix, flag) {
  
  while(1) {
    // console.log(max, y, x, flag);
    if(x+max-1 > matrix[0].length-1 || y+max-1 > matrix.length-1) return max-1;
    
    for(let i=0; i<max; i++) {
      for(let j=0; j<max; j++) {
        if(matrix[y+i][x+j] === 0) {
          flag = false;
          break;
        }
      }
    }
    if(!flag) return max-1;
    
    if(flag) max++;
  }
}

function solution(board) {
  let answer = 0;

  for(let i=0; i<board.length; i++) {
    for(let j=0; j<board[0].length; j++) {
      // console.log(i,j);
      answer = Math.max(answer, isRight(1, i, j, board, true))
    }
  }
  return answer*answer;
}

console.log(solution([
  [0, 1, 1, 1], 
  [1, 1, 1, 1], 
  [1, 1, 1, 1], 
  [0, 0, 1, 0]]));

console.log(solution([
  [0, 0, 1, 1], 
  [1, 1, 1, 1]]));

다른 풀이

동적계획법을 사용한 풀이

나는 board[0][0]에서 시작했다. 그러다보니 이전 값들에 대한 정보를 저장할 생각을 못 했다.
board[1][1]에서 시작해서 top,left/cross에 대한 정보들을 받는다.
이중 최소값+1을 현재값인 board[i][j]에 저장해나간다.

예를 들어,
기본값은 0과 1이다.
세 값 중 하나라도 0이 있으면(0이 제일 작은 값이면) 4개가 1이 될 수 없으므로 현재 board[i][j]는 1밖에 안 된다.
세 값 중 최소값이 1이면 4개가 1을 무조건 갖고 있으므로 board[i][j]는 2가 될 수 있다.
...
이런식으로 이전 4개 값에 대한 정보를 전부 저장해서 완전탐색을 진행하면 된다.

이해하는 데 도움을 받은 이미지 출처

function solution(board) {
  let answer = 0;
  let row = board.length;
  let col = board[0].length;
  
  if(row < 2 || col < 2) return 1;
  

  for(let i = 1; i < row; i++) {
    for(let j = 1; j < col; j++) {

      if(board[i][j] !== 0) {
        const cross = board[i-1][j-1]
        const top = board[i-1][j]
        const left = board[i][j-1]

        const min = Math.min(cross, top, left);
        board[i][j] = min + 1;
      }

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