[python] 백준 1051번

문제링크 : www.acmicpc.net/problem/1051 

내 풀이(틀린 코드)
꼭짓점의 숫자가 모두 같은 정사각형을 구하면 되는 문제였다.
때문에 모든 경우의 수를 계산해야하며 조건에 부합하는지는 bfs탐색을 이용했다.
시작 좌표값을 기준으로 x, y 1칸씩 이동하며, 나머지 꼭짓점은 시작좌표와 이동된 좌표를 섞어서 확인하는 방식이다.
흠 그런데 41%에서 막혔다... ㅜㅜ 

# silver 3
import sys
sys.stdin = open("input.txt","r")
input = sys.stdin.readline
n, m = list(map(int,input().split()))

arr = []
for i in range(n):
    arr.append(list(map(str,input())))
ans = 0 # 갯수
def bfs(sx,sy):
    visited = [[False for j in range(m)] for i in range(n)]
    queue = []
    queue.append((sx,sy))
    global ans
    visited[sy][sx] = True
    while queue:
        x, y = queue.pop(0)
        if (sx != x and sy != y) and arr[sy][sx] == arr[y][x] == arr[sy][x] == arr[y][sx]:
            ans = max(ans,(x-sx+1)*(y-sy+1))
        if x+1 <= m-1 and y+1 <=n-1:
            nx = x+1
            ny = y+1 
            if visited[ny][nx] == False:
                visited[ny][nx] = True
                queue.append((nx,ny))
for y in range(n):
    for x in range(m):
        bfs(x,y)
print(ans)

다른 사람 풀이
다른 사람 풀이를 확인해보니까 탐색을 사용하지않고, 정사각형이 만들어질 수 있는 x, y의 변위 조건을 통해 접근하더라. 정사각형의 한 변의 길이는 N*M 직사각형에서 가장 작은 한 변의 길이까지만 가능하다. k는 0부터 시작하지만 (0,0)을 포함한 1개의 정사각형도 가능하므로 k+1이 정사각형의 한 변의 길이가 된다.

import sys
sys.stdin = open("input.txt","r")
input = sys.stdin.readline
n, m = map(int,input().split())
arr = [list(map(str, input())) for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        for k in range(m if n > m else n):
            if i+k < n and j+k < m:
                if arr[i][j] == arr[i+k][j] == arr[i][j+k] == arr[i+k][j+k]:
                    ans = max(ans, (k+1)*(k+1))
print(ans) 

구현 너무 어렵다... 최대한 단순하게 생각해야 잘 풀리는것 같은데 자꾸 알고리즘부터 떠올리는 습관이 되려 구현 문제를 더 복잡하게 하는 것 같다 ㅜㅜ 연습하자..