99클럽 코테 스터디 _ 12일차 TIL (브루트 포스)

 

< 문제 >

[백준] 1051. 숫자 정사각형 / 실버3

---

< 풀이 >

코드 변수 정의

• min(N, M) : 만들 수 있는 정사각형 한 변의 최대 길이

---

Brute Force
시간복잡도 : O(N x M x min(N, M))             *최악의 경우

def f():
    N, M = map(int, input().split())
    board = [input() for _ in range(N)]

    for s in range(min(N, M), 1, -1): # 주어진 보드로 만들 수 있는 모든 정사각형의 한변의 길이
        for i in range(N - s + 1):
            for j in range(M - s + 1):
            	# 정사각형 4개 모서리가 모두 같은 값을 갖는 경우
                if board[i][j] == board[i+s-1][j] == board[i][j+s-1] == board[i+s-1][j+s-1]:
                    return s * s  # 정사각형 크기 반환
    return 1 # 정사각형 크기의 최소값

print(f())

 

 

 

풀이 방식

1. 정사각형의 가능한 최대 크기부터 검사
   • 한 변의 길이가 min(N, M)인 정사각형이 가장 큰 정사각형이다.
   • 가장 큰 정사각형부터 시작하여 2까지 감소하면서 네 모서리를 확인한다.
   • 최대 크기부터 검사하기 때문에 최소 크기까지 갈 필요 없이 찾은 순간 바로 최댓값을 반환한다.
2. 각 위치에서 정사각형 확인
   • 크기별로 정사각형의 왼쪽 상단 모서리가 위치할 수 있는 행과 열을 기준으로 탐색한다.
   • 정사각형의 네 모서리(좌측 상단, 좌측 하단, 우측 상단, 우측 하단)이 같은 값을 가지는 지 확인한다.
   • 네 모서리가 같은 값을 가지면 정사각형 크기(s * s)를 반환한다.
3. 정사각형 크기의 최솟값
   • 한 변의 길이가 2인 정사각형까지 검사했을 때 조건을 만족하는 정사각형이 없는 경우, 최솟값인 1을 반환한다.

---

< 회고 >

🤔 💭_

문제를 보자마자 주어진 보드의 크기를 기준으로 만들 수 있는 정사각형 한 변의 길이로 풀이를 해야겠다고 생각했다.

처음에는 반환할 max값을 1로 초기화한 후, 사이즈를 키워가며 현재 max값과 비교하는 식으로 풀었다. 생각해 보니 max값을 따로 두지 않고 큰 사이즈부터 사이즈를 줄여가며 조건을 만족한 경우 사이즈를 반환하면 그 값이 최댓값이 된다는 것을 깨달았다.

 

불필요한 함수 및 변수를 줄일 수 있었다.