[python] 1051- 숫자 정사각형

1051번: 숫자 정사각형 (acmicpc.net)

1051번: 숫자 정사각형

 

완전 탐색으로 해결하였다.

처음에는 테스트케이스를 다 통과했는데도 통과하지 못해서 고민하다가 반례를 찾아보았다.

글 읽기 - 단언컨대 반례가 없습니다. 그런데 틀리네요 (acmicpc.net)

질문 게시판에서 너무 웃긴 반례를 발견하고 적용해본 후 문제점을 알 수 있었다.

정사각형 판별 함수에서 모든 조건을 검색한 후 max 값을 return 해야 하는데

정사각형을 찾자마자 return 해버려서 답이 틀렸던 거였다.

 

테케는 오묘하게 그런 반례들을 확인할 수가 없었다.

이런 경우들이 부쩍 많은 거 같아서 문제를 꼼꼼하게 읽고 분석하는 연습을 해야될 것 같다.

집중 코딩!

 

 

# 1051 숫자 정사각형
import sys
input = sys.stdin.readline

# 정사각형 판별 함수
def chk(i,j):
    x = rac[i][j]
    tmp=1
    for idx in range(1, min(n,m)):
        if i+idx >= n or j+idx >= m:
            continue
        
        y = rac[i][j+idx]
        x2 = rac[i+idx][j]
        y2 = rac[i+idx][j+idx]
        
        if x == y == x2 == y2:
            tmp = max((idx+1)**2, tmp)
    
    return tmp
        
# main 함수
n, m = map(int, input().split())

rac = list()
for i in range(n):
    rac.append(list(input()))
    
size=1
for i in range(n-1):
    for j in range(m-1):    
        size= max(size, chk(i, j))
            
print(size)

 

 

* 모든 코드는 github에서 관리합니다.  seinShin (SEIN SHIN) (github.com)

seinShin - Overview