[LeetCode] 221번 - Maximal Square [Swift]

문제 링크

Maximal Square - LeetCode

문제

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output: 4

 

Example 2:

Input: matrix = [["0","1"],["1","0"]]

Output: 1

 

Example 3:

Input: matrix = [["0"]]

Output: 0

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

문제 풀이

이 문제는 주어진 배열에서 값이 모두 1인 정사각형 중 가장 큰 정사각형을 찾는 문제입니다.

제일 처음엔 간단하게 완전 탐색을 해서 풀었는데 통과가 되긴 하지만 다른 방법이 없을까 해서 알아보던 중 DP를 활용한 방법이 있어 정리해보려고 합니다.

 

만약 위와 같이 배열이 주어진다면 1로 이루어진 가장 큰 정사각형을 어떻게 찾을 수 있을까요?

사람인 저희는 그냥 바로 3*3 크기의 정사각형을 찾아버리겠지만, 컴퓨터는 그럴 수 없어요 ㅠ.ㅠ

이걸 DP로 처리하는 방법은 이렇습니다.

 

DP[i][j]에는 해당 위치에 만들 수 있는 정사각형의 최대 사이즈가 저장됩니다.

이걸 저장하기 위해선 아래와 같은 과정을 처리해주시면 됩니다.

1. 주어진배열[i][j]의 값이 "1"인지 확인합니다.
2. 만약 "1"이라면 최소 1*1 사이즈의 정사각형은 만들 수 있기 때문에 확인해줘야 합니다.
3. dp[i][j-1], dp[i-1][j-1], dp[i-1][j] 에서 가장 작은 값을 찾고 그 값에 1을 더해줍니다.
4. 결괏값과 지금 만들어진 값 중 더 큰 값을 결괏값에 저장합니다.

근데 여기서 0행, 0열의 경우엔 위의 과정을 처리할 수 없기 때문에 주어진 배열보다 1행, 1열씩 더 큰 배열로 DP 배열을 구성해주시면 됩니다.

위와 같이 준비를 한 뒤에 아까 위의 과정을 해주면 됩니다.

위의 과정을 자세히 한 번 보기 위해 DP[2][2] 부분을 실제로 한 번 해보겠습니다.

위와 같이 DP[2][2]를 구할 수 있는데요, 구하는 위치의 위, 왼쪽, 왼쪽 대각선 값의 최솟값을 구하는 이유는 주변에서 만들 수 있는 정사각형이 있다면 현재 구하고자 하는 위치에도 정사각형이 존재할 수 있기 때문이에요.

 

즉 DP[1][1]에서 1*1 크기의 정사각형을, DP[1][2]에서 1*1 크기의 정사각형을, DP[2][1]에서 1*1 크기의 정사각형을 만들 수 있기 때문에 현재 구하고자 하는 위치인 DP[2][2] 위치에서 만들 수 있는 정사각형의 크기는 여기서 +1을 한 2*2 크기가 되는 것입니다.

 

여기서 최솟값을 구해주는 이유는 아무리 어떤 값에서 큰 정사각형을 만들 수 있다고 하더라도 현재 구하고자 하는 위치에서 정사각형을 만들기 위해서는 세 방향 모두에서 만들 수 있는 정사각형이 필요하기 때문이죠.

 

예를 들어 세 방향 중 하나라도 0이 존재한다면 DP[i][j] = min(0) + 1로 1*1 크기의 정사각형만 만들 수 있게 됩니다.

소스 코드

완전 탐색

// 완전 탐색
func maximalSquare(_ matrix: [[Character]]) -> Int {
    var windowSize: Int = 1
    var result: Int = 0
    let n: Int = matrix.count
    let m: Int = matrix[0].count
        
    func isValid(start: [Int]) -> Bool {
        if start[0] + windowSize - 1 >= n || start[1] + windowSize - 1 >= m {
            return false
        }
        for i in start[0]..<start[0]+windowSize {
        	for j in start[1]..<start[1]+windowSize {
        		if matrix[i][j] == "0" {
                	return false
                }
            }
        }
        return true
    }
        
    while windowSize <= max(n,m) {
        var valid: Bool = false
        for i in 0..<n {
            for j in 0..<m {
                valid = isValid(start: [i,j])
                if valid {
                    break
                }
            }
            if valid {
                result = max(result, windowSize * windowSize)
                break
            }
        }
        windowSize += 1
    }
    
    return result
}

DP

// DP
func maximalSquare(_ matrix: [[Character]]) -> Int {
	let m = matrix[0].count
    let n = matrix.count
    var result: Int = 0
        
    var dp: [[Int]] = [[Int]](repeating: [Int](repeating: 0, count: m+1), count: n+1)
        
    for i in 1...n {
        for j in 1...m {
            if matrix[i-1][j-1] == "1" {
                dp[i][j] = min(min(dp[i][j-1], dp[i-1][j-1]), dp[i-1][j]) + 1
                result = max(result, dp[i][j])
            }
        }
    }
        
    return result * result
}