https://www.acmicpc.net/problem/1915
1915번: 가장 큰 정사각형
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
www.acmicpc.net
dp문제다. 완전 탐색으로 시도했지만 역시나 시간 초과. 점화식을 생각해내는 데에 시간이 걸렸던 문제다.
풀이
최소한의 정사각형을 만들 수 있는 칸부터 시작해야 한다. 2차원 배열 map에 대해서 x와 y의 값이 모두 1 이상이고 map[x][y]의 값이 0보다 커야 한다. 해당 좌표의 상, 좌, 좌대각선 칸 중 최솟값 + 1로 갱신해나가면 된다.
map[x][y] = min(min(map[x-1][y], map[x][y-1]), map[x-1][y-1]) + 1
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import Foundation | |
| let nm = readLine()!.split(separator: " ").map{Int($0)!} | |
| let n = nm[0] | |
| let m = nm[1] | |
| var map = Array(repeating: Array(repeating: 0, count: m), count: n) | |
| var visited = Array(repeating: Array(repeating: false, count: m), count: n) | |
| var ans = 0 | |
| for i in 0..<n{ | |
| let line = readLine()!.map{Int(String($0))!} | |
| for k in 0..<m{ | |
| map[i][k] = line[k] | |
| if map[i][k] == 1{ | |
| ans = 1 | |
| } | |
| } | |
| } | |
| if n>1 && m>1{ | |
| for i in 1..<n{ | |
| for k in 1..<m{ | |
| if map[i][k] > 0{ | |
| map[i][k] = min(min(map[i-1][k], map[i][k-1]), map[i-1][k-1]) + 1 | |
| ans = max(ans, map[i][k]) | |
| } | |
| } | |
| } | |
| } | |
| print(ans*ans) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [1148] 단어 만들기 (0) | 2022.11.03 |
|---|---|
| [1195] 킥다운 (1) | 2022.11.02 |
| [1347] 미로 만들기 (0) | 2022.10.31 |
| [1388] 바닥 장식 (0) | 2022.10.31 |
| [1063] 킹 (1) | 2022.10.28 |