📜문제 설명

문제 바로가기

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

📍입력

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

3 5
42101
22100
22101

2 2
12
34

📍출력

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

9

1

---

📄문제 해결

📝내가 푼 코드

✅ 1차 시도 => 성공!

# 메모리: 109544KB / 시간: 100ms

def func():
    N, M = map(int, input().split(' '))
    case = [list(input()) for _ in range(N)]

    for n in range(min(N, M), 1, -1): # 정사각형 한 변의 길이
        for i in range(N-n+1):
            for j in range(M-n+1):
                if (case[i][j] == case[i+n-1][j]) and (case[i][j] == case[i][j+n-1]) and (case[i+n-1][j] == case[i+n-1][j+n-1]):
                    return n*n
    
    return 1   # 끝까지 못 찾는 경우

print(func())

일단 이번 주 문제는 완전탐색임을 알기도 했지만, 문제를 읽어보곤 이건 무조건 가능한 가장 큰 정사각형부터 가장 작은 2*2인 정사각형까지 모든 경우의 수를 탐색해야하는 문제임을 알 수 있었다.

N과 M 입력을 받고, 작은 수를 가장 큰 정사각형의 한 변의 길이(n)로 하며, i와 j는 정사각형의 왼쪽 위 점이다. 로직은 단순한데, 직사각형을 탐색하며 정사각형의 왼쪽 위 점과 오른쪽 위 점, 왼쪽 위 점과 왼쪽 아래 점, 왼쪽 아래 점과 오른쪽 아래 점을 비교하여 모든 점의 값이 같은지 확인하여 같으면 정사각형의 넓이를 return한다.

이때, return을 활용해 3중인 반복문을 한 번에 탈출할 수 있도록 하기 위해 함수로 구현하였고, 모든 반복문을 돌아도 넓이를 return하지 않아 함수를 탈출하지 않은 경우에는 1을 return한다.

---

🤔느낀점

이번에 푼 문제는 생각보다 간단하고 쉽게 풀리는 완전탐색 문제였다. 직사각형 안에서 i, j와 n을 활용해 적절한 인덱스 값을 계산하는 것이 조금 헷갈렸으나 다행히 24분 안에 문제를 해결할 수 있었다!