[백준(BOJ)] 4095 최대 정사각형 - 스위프트(Swift)

[Gold IV] 최대 정사각형 - 4095

문제 링크

성능 요약

메모리: 77036 KB, 시간: 2476 ms

분류

다이나믹 프로그래밍

문제 설명

1과 0으로 이루어진 NxM크기의 행렬이 주어졌을 때, 1로만 이루어진 가장 큰 정사각형 부분 행렬 찾는 프로그램을 작성하시오.

입력

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 개가 주어진다.

출력

각 테스트 케이스에 대해서 가장 큰 정사각형의 너비 또는 높이를 출력한다. 만약 그런 정사각형이 없을 때는 0을 출력한다.

 

풀이

i)

DP문제로, 현재 인덱스 값이 1이라면 현재 인덱스를 기준으로 왼쪽, 위쪽, 왼쪽 위 대각선의 값 중 최소값 +1로 채워나가면 값을 구할 수 있습니다.

 

예시를 확인해보겠습니다.

4 5
0 1 0 1 1
1 <1> 1 1 1
0 1 [1] 1 0
1 1 1 1 1

dp 배열
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

왼쪽 상단을 [0, 0]으로 생각하고 오른쪽과 밑으로 순환하면서 값들을 비교하는 것입니다.

 

위에서 설명드렸다싶이 만약 1을 만난다면 왼쪽, 위쪽, 왼쪽 위 대각선의 값 중 최소값에 +1을 더한 값으로 설정하면 됩니다. 첫째 줄은 배열에 들어있는 값으로 설정해주면 됩니다.

 

예를 들어 만약 <1>을 만났을 때, 왼쪽, 위쪽, 왼쪽 위 대각선 값 중 최소값은 0이기 때문에([0,0]) 0 + 1인 1을 해당 dp배열에 대입하면 됩니다.

dp 배열
0 1 0 1 1
1 <1> 0 0 0
0 0 0 0 0
0 0 0 0 0

 

그러다가 [1]을 만난다면, 왼쪽, 위쪽, 왼쪽 위 대각선 중 최소값이 1이기 때문에 1 + 1인 2가 되는 것입니다.

dp 배열
0 1 0 1 1
1 1 1 1 1
0 1 <2> 0 0
0 0 0 0 0

위처럼 진행하게 되면 정사각형의 최대값을 구할 수 있습니다.

 

while true {
    let inputValues = readLine()!.split(separator: " ").map { Int($0)! }
    let N = inputValues[0]
    let M = inputValues[1]
    
    if N == 0 && M == 0 {
        break
    }
    
    var dp = [[Int]](repeating: [Int](repeating: 0, count: M), count: N)
    
    for x in 0..<N {
        let tempValues = readLine()!.split(separator: " ").map { Int($0)! }
        for y in 0..<M {
            dp[x][y] = tempValues[y]
        }
    }
        
    var result = 0
    
    for x in 0..<N {
        for y in 0..<M {
            if dp[x][y] == 1 {
                if x > 0 && y > 0 { //첫번째 줄 제외
                    dp[x][y] = min(dp[x-1][y], dp[x][y-1], dp[x-1][y-1]) + 1    //왼쪽, 위쪽, 왼쪽 위 대각선 확인
                }
                if result < dp[x][y] {
                    result = dp[x][y]
                }
            }
        }
    }
    
    print(result)
}