[Algorithm/Programmers] 가장 큰 정사각형 찾기 Swift

가장 큰 정사각형 찾기 Level2

문제 풀이: 

이 문제는 처음에 완전탐색으로 접근했다가 푸는 방법을 모르겠어서 해설을 참고했다.

Dynamic Programming을 이용해서 문제를 풀어야 한다. 

 

n이라고 써져 있는 1을 기점으로 박스친 곳에서 최소의 숫자를 구해서 n에 더해준다. 

그런 식으로 값을 모두 구하면서 제일 큰 값을 구한다. 

그리고 그 값의 제곱을 하면 넓이가 나오게 된다.

 

코드:

import Foundation

func solution(_ board:[[Int]]) -> Int
{
    var board = board
    var result = 0
    
    if board.count == 1 {
        return 1
    }
    
    for i in 1..<board.count {
        for j in 1..<board[i].count {
            if board[i][j] != 0 {
                board[i][j] += min(board[i-1][j], board[i][j-1], board[i-1][j-1])
                result = max(result, board[i][j])
            }
        }
    }
    
    return result * result
}

문제:

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

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