[백준] 1051번: 숫자 정사각형 - 파이썬/python

 

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

1051번: 숫자 정사각형

접근 방식

- 효율적인 그래프 검사 방법 구상

- 함수 활용 여부 고민

 

코드 풀이

n, m = map(int, input().split())
graph = []
for _ in range(n):
    tmp = list(input())
    graph.append(tmp)
    
s_max = min([n, m]) # 가능한 정사각형의 최대 변의 길이

def check(graph, s):
    flag = 0
    for i in range(len(graph)-s+1):
        for j in range(len(graph[0])-s+1):
            if graph[i][j] == graph[i+s-1][j] == graph[i][j+s-1] == graph[i+s-1][j+s-1]:
                flag = s*s
                return flag
                break # graph에서 s인 정사각형을 하나라도 찾으면 더 찾지 않음
    return 0 # 한 변의 길이가 s인 정사각형이 존재하지 않는 경우
                
answer = [] # 가능한 정사각형의 넓이 리스트
for lnth in range(1, s_max+1):
    if check(graph, lnth) != 0:
        answer.append(check(graph, lnth))
        
print(max(answer))

먼저 input을 차례로 변환하여 그래프를 생성했습니다. 문자열 형태로 input이 들어오므로 이를 리스트 처리함으로써 알파벳 하나하나가 원소가 될 수 있도록 했습니다. 그리고 그래프(graph)와 관심 있는 한 변의 길이(s)가 주어졌을 때, 해당 길이를 한 변으로 하는 정사각형이 존재하는지 확인할 수 있는 check 함수를 생성해, 1부터 최대 가능한 s까지 check함수의 input으로 활용하는 형태로 코드를 작성했습니다. 

check 함수는, 정사각형의 왼쪽 위 꼭지점을 graph[i][j]로 하는 인덱스 i, j의 범위 안에서, 네 개의 꼭짓점의 값이 모두 같은지 확인함을 목적으로 합니다. 예를 들어 graph가 graph[0]0] 부터 graph[2][4]의 범위를 가진다면, 가능한 i, j 인덱스의 범위는  graph[0][0]부터 graph[0][2] 입니다. 정사각형의 존재가 확인되는 경우 넓이를 return해주고 그렇지 않은 경우 0을 return합니다. 함수는 추후 가능한 s의 범위 내에서 모두 탐색되며 각각의 값에서의 return값이 0이 아닌 경우 answer 리스트에 저장되게 됩니다. 마지막으로 가능한 최대 크기에서의 정답을 출력합니다.

 

오답 이유

- check 함수를 생성할 때 4개의 꼭짓점의 수가 모두 같은 경우, s*s인 flag 값을 return해줍니다. 이때 한 변의 길이가 s인 정사각형을 graph에서 찾지 못하는 경우가 있는데, 이러한 경우를 따로 정의하지 않는 경우 NoneType을 return하게 됩니다. 이 경우, 코드 마지막줄에서 에러가 발생하게 되는데, max 등의 연산자는 int에서만 활용할 수 있기 때문입니다. 따라서 한 변의 길이가 s인 정사각형이 존재하지 않는 경우는 else로 따로 빼 0을 return하는 방식으로 코드를 변형했습니다.

- 또한, s=1인 경우를 고려하지 못해 오답이 발생했습니다. 이는 check 함수에 들어가는 lnth의 범위를 조정함으로써 해결했습니다.