[Algorithm/Swift] 프로그래머스(Lv.2) - 가장 큰 정사각형 찾기

안녕하세요 제인입니다!

PS..를 들고 왔습니다....혼자 해결못한 문제가 또 생긴 것이죠..예..

PS 실력이 왜 이렇게 안늘까요....좀 더 많은 문제를 풀어봐야겠어요..

문제 링크

프로그래머스

문제 풀이

일단 이 문제는 DP(Dynamic Programming) 알고리즘을 이용해 풀어야하는 문제였습니다.

1915번: 가장 큰 정사각형

프로그래머스의 연습문제라 백준에도 동일한 문제가 있습니다!

이 문제는 간단하지만 DP 문제의 대표적인 유형(?) 같아서 나중에 비슷한 유형의 문제가 나왔을 때 응용할 수 있도록 기록해두면 좋을 것 같습니다! (DP문제는 이 문제를 DP로 풀어야겠다는 감이 잘 안오는 문제가 많더라구요..)

 

저는 처음에 접근을 dfs로 했는데요,, dfs 함수를 만들어서 방문하지 않은 좌표이고 1이라면 해당 좌표의 오른쪽, 아래쪽을 확인해서 값을 더해주는 방식(재귀로 반복)으로 연결된 사각형의 최댓값을 구한 다음, 사각형 영역 이외의 좌표의 값이 포함되어있을 수 있으니 앞의 과정에서 도출한 최댓값보다 작은 가장 가까운 제곱근을 구해서 다시 제곱해주는 방식으로 풀었습니다,,

근데 코드를 짜고 보니 이미 방문한 좌표는 다시 방문하지 않기 때문에 정사각형이 나올 수 있는 모든 경우의 수 체크가 어렵고, 어떤 좌표를 먼저 방문했는지에 따라 결과값이 달라질 수 있겠다는 생각을 하게 되었고... 다른 풀이 방법이 떠오르지 않아 그냥 풀이 방법을 찾아봤던 것 같아요..ㅎ

 

이 문제를 DP를 이용해 해결하는 법을 쉽게 이해가 가도록 그림으로 봅시다!

문제에 제시된 입출력 예제 1번의 입력값을 가지고 풀이해보도록 하겠습니다~!

이런 사각형이 주어진다면, 이 사각형 내에서 전부 1로 이루어진 가장 큰 정사각형을 찾는 방법은 크기가 2*2인 정사각형(1개 이상의 칸을 가지고 만들 수 있는 가장 작은 정사각형 크기)을 하나씩 확인해가며 최대 넓이를 구하는 것입니다. 

arr[1][1] 부터 좌표의 값을 확인하며 해당 좌표의 값이 1이라면 현재 정사각형 범위(arr[i-1][j], arr[i][j-1], arr[i-1][j-1]) 안에 있는 가장 작은 수를 arr[i][j] 에 더해서 현재까지 확인한 정사각형들의 한 변의 길이의 최댓값을 갱신해가는 방식으로 같은 연산을 반복하지 않고 효율적으로 답을 도출해낼 수 있습니다.

 

이러한 방식으로 답을 도출해나가는 과정을 그림으로 보면 쉽게 이해가 될 것 같습니다!

(1,1) 부터 시작해서 2*2 정사각형을 확인합니다. 위의 사각형의 경우 최솟값이 0이기 때문에 (1,1)의 값은 그대로 1이 됩니다. 

최솟값을 더하는 이유는 위의 경우와 같이 최솟값이 0인 경우 해당 범위의 사각형이 모두 1로 이루어져있지 않다는 의미이기 때문에 사각형의 변의 길이를 업데이트 시켜주지 않기 위해서 입니다!

arr의 인덱스를 순회하면서 첫번째 과정을 반복하면 위와 같은 과정으로 값이 저장되게 됩니다.

위의 그림까지 앞의 과정을 반복하게 되면 (2,3)에 저장되는 값은 3이 되므로, 주어진 사각형에서 구할 수 있는 가장 큰 정사각형의 한 변의 길이가 저장됩니다. 결과를 도출할 때 이 값에 제곱을 해서 리턴해주면 되겠죠!!

주어진 2차원 배열을 끝까지 순회하게 되므로 위의 과정이 추가가 되겠지만, 순회가 끝난 후 좌표에 저장되는 최댓값은 그대로 3이므로 원하는 결과값인 최댓값을 구할 수 있습니다. 이러한 과정을 Swift 코드로 나타내면 다음과 같습니다.

Swift 풀이 코드

import Foundation

func solution(_ board:[[Int]]) -> Int {
    var arr = board
    var max = 0
    
    // 행이나 열 길이 1인 경우 따로 처리
    if board.count == 1 || board[0].count == 1 {
        max = board.flatMap{$0}.contains(1) ? 1 : 0
    }
    
    for i in 1..<board.count {
        for j in 1..<board[0].count {
            if arr[i][j] == 1 {
                let min = [arr[i-1][j-1], arr[i-1][j], arr[i][j-1]].min()! // 2*2 정사각형 중 최솟값
                arr[i][j] += min // 해당 좌표에 최솟값 더함
                max = arr[i][j] > max ? arr[i][j] : max // max값 갱신
            }
        }
    }

    return max * max
}

---

[참고 자료]

https://velog.io/@leeesangheee/Level-2-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95-%EC%B0%BE%EA%B8%B0-Swift

https://gimjinging.tistory.com/82

https://babbab2.tistory.com/131