[swift] 백준 - 1050번: 숫자 정사각형

문제 링크

1051번: 숫자 정사각형

---

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

예제

---

성공 풀이

import Foundation

let I = readLine()!.split {$0==" "}.map {Int($0)!}, N = I[0], M = I[1]
var arr = (0..<N).map { _ in Array(readLine()!).map {Int(String($0))!}}
var result = 1

for size in 1..<min(N,M) {
    for y in 0..<N-size {
        for x in 0..<M-size {
            let p1 = arr[y][x]
            let p2 = arr[y][x+size]
            let p3 = arr[y+size][x]
            let p4 = arr[y+size][x+size]
            
            if p1 == p2 && p2 == p3 && p3 == p4 {
                result = (size+1)*(size+1)
            }
        }
    }
}
print(result)

풀이 키워드

• 3개의 반복문을 중첩해서 풀 수 있었습니다.
• 먼저 변의 길이가 2인 정사각형부터 최대길이를 가진 정사각형 까지 탐색했습니다.
• 탐색 과정에 정사각형을 만들 수 있는 꼭지점을 지정하기 위해 2중 반복문으로 (y,x)를 구해 (y,x)로부터 size만큼 떨어지 3꼭지점을 구해 4꼭지점이 모두 동일한지 검사했습니다.