[baekjoon] 1051번 숫자 정사각형

출처

---

https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

 

 

문제

---

N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다.

이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오.

이때, 정사각형은 행 또는 열에 평행해야 한다.

 

 

입력

---

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에 수가 주어진다.

 

 

출력

---

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

 

 

풀이 및 코드

---

예전 J's code challenge를 하며 푼 문제와 유사해서 쉽게 풀 수 있었던 구현 문제였다.

직사각형 안에서 만들 수 있는 가장 큰 정사각형을 찾야야 하므로

N과 M 중 작은 값 K부터 주어지는 직사각형에서 정사각형을 만들 수 있다.

이중 forloop를 통해 K의 가능 여부를 판별 후, 안될 경우 계속 K값을 1씩 줄여가는 방식으로 확인하면 된다.

 

def find_square(k):
    # 이중 forloop로 k의 가능 범위 모두 확인
    for i in range(n-k+1):
        for j in range(m-k+1):
            # 조건에 부합하면 True return
            if graph[i][j] == graph[i][j+k-1] == graph[i+k-1][j] == graph[i+k-1][j+k-1]:
                return True
    return False

n,m = map(int, input().split())
# n,m 중 작은 값 k부터 정사각형을 만들 수 있음
k = min(n,m)
graph = []
for _ in range(n):
    graph.append(list(map(int,input())))

while True:
    if find_square(k):
        print(k**2)
        break
    # 현재 k로 정사각형을 못 만들 경우, -1
    k -= 1