1051. [Python]숫자 정사각형

1. 문제

 

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

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 구현

 

3. 파이썬 코드

 

N, M = map(int,input().split())

matrix = [ list(map(int,input())) for _ in range(N)]
# 최대 결과값이 1이 될 수 있으므로 1을 베이스로 시작
result = [1]
# 브루트포스 시작
for i in range(N):
    for j in range(M):
        # 꼭지점 계산을 위한 초기값 선언
        current = 1
        # 범위 내에 존재하면 계속 반복문 진행
        while i+current < N and j+current <M:
            # 각 꼭지점 값 비교
            if matrix[i][j] == matrix[i][j+current] and matrix[i][j] == matrix[i+current][j] and matrix[i][j] == matrix[i+current][j+current]:
                # 모두 같은경우 길이를 추가
                result.append(current+1)
            # 계속해서 범위를 늘려나감
            current += 1

# 최대 길이 도출
answer = max(result)
# 길이값 추가
print(answer**2)

 

4. 문제를 풀고난 후 생각

 

• N, M 값이 크지 않고 모든 경우의 수를 탐색해야기 때문에 브루트 포스를 선택
• 브루트 포스 알고리즘을 선택하며 정사각 형이 되야하기 때문에 각 꼭지점을 균등하게 증가시키는 변수를 생성해줬다.
• 범위 내의 모든 값들을 탐색을 하며 꼭지점 값들을 비교하며 일치하는 경우 그 길이를 결과 리스트에 추가했다.
• 모든 탐색이 끝나고 결과 리스트에서 max 값을 뽑아낸 후 크기를 출력해주면 된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트 포스