백준 1915 가장 큰 정사각형

출처: www.acmicpc.net/problem/1915

분류: DP

---

접근방식

문제 이름처럼 만들 수 있는 가장 큰 정사각형을 찾는 문제입니다.

정사각형의 성질을 생각해보면 DP와 재귀를 활용해 정사각형의 크기를 쉽게 구해낼 수 있습니다.

정사각형은 다른 정사각형의 모음입니다. 

3x3짜리 정사각형을 예로 들어볼까요?

각 칸에 정사각형의 크기를 적어보면 다음과 같습니다.

3	2	1
2	2	1
1	1	1

 

여기서 하나가 빠져서 아깝게 정사각형이 못되는 경우를 생각해보면 다음과 같습니다.

2	2	1
2	1	1
1	1	0

 

규칙이 보이시나요? 정사각형은 자신을 둘러싸고 있는 정사각형들의 크기 중 가장 작은 값 + 1 만큼이 자신의 크기입니다.

위 예처럼 하나만 빠져도 정사각형이 될 수 없기 때문이죠!

이 성질을 이용하면 자신을 둘러싸고 있는 3칸만 재귀적으로 확인해주면 가장 큰 정사각형의 크기를 쉽게 구할 수 있습니다 :)

func square(_ p: Point) -> Int {
  ...
  if map[p.r+1][p.c] == "1", map[p.r][p.c+1] == "1", map[p.r+1][p.c+1] == "1" {
      size[p.r][p.c] = min(square((p.r+1, p.c)), square((p.r, p.c+1)), square((p.r+1, p.c+1))) + 1
  }
  ...
}

 

해결방법

typealias Point = (r: Int, c: Int)
let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (nm[0], nm[1])

var map = [[Character]]()

for _ in 0..<n {
    map.append(Array(readLine()!))
}

var size = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)

func square(_ p: Point) -> Int {
    guard size[p.r][p.c] == 0 else { return size[p.r][p.c] }
    size[p.r][p.c] = 1
    
    guard p.r+1 < n, p.c+1 < m else { return size[p.r][p.c] }
    
    if map[p.r+1][p.c] == "1", map[p.r][p.c+1] == "1", map[p.r+1][p.c+1] == "1" {
        size[p.r][p.c] = min(square((p.r+1, p.c)), square((p.r, p.c+1)), square((p.r+1, p.c+1))) + 1
    }
    
    return size[p.r][p.c]
}


var maxSize = 0
for r in 0..<n {
    for c in 0..<m where map[r][c] == "1" {
        let s = square((r, c))
        maxSize = max(maxSize, s*s)
    }
}

print(maxSize)

 

배운점