티스토리 뷰
문제 링크
문제
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]에는 해당 위치에 만들 수 있는 정사각형의 최대 사이즈가 저장됩니다.
이걸 저장하기 위해선 아래와 같은 과정을 처리해주시면 됩니다.
- 주어진배열[i][j]의 값이 "1"인지 확인합니다.
- 만약 "1"이라면 최소 1*1 사이즈의 정사각형은 만들 수 있기 때문에 확인해줘야 합니다.
- dp[i][j-1], dp[i-1][j-1], dp[i-1][j] 에서 가장 작은 값을 찾고 그 값에 1을 더해줍니다.
- 결괏값과 지금 만들어진 값 중 더 큰 값을 결괏값에 저장합니다.
근데 여기서 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
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode] 739 - Daily Temperatures [Swift] (0) | 2021.05.04 |
---|---|
[LeetCode] 5번 - Longest Palindromic Substring [Swift] (0) | 2021.02.28 |
[LeetCode] 105번 - Construct Binary Tree from Preorder and Inorder Traversal [Swift] (0) | 2021.02.24 |
[LeetCode] 102번 - Binary Tree Order Traversal [Swift] (0) | 2021.02.24 |
[LeetCode] 94번 - Binary Tree Inorder Traversal [Swift] (0) | 2021.02.18 |
- Total
- Today
- Yesterday
- 백준
- Publisher
- OS
- mac
- 프로그래밍
- IOS
- 앱개발
- System
- 테이블뷰
- 동시성
- Swift
- operator
- 아이폰
- OSTEP
- 문법
- pattern
- Apple
- dfs
- design
- operating
- DP
- Xcode
- BFS
- document
- 코딩테스트
- 스위프트
- 코테
- Combine
- 자료구조
- 알고리즘
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |