[백준 1051] 숫자 정사각형 (python)

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

1051번: 숫자 정사각형

숫자 정사각형 문제

한칸당 한자리 숫자로 주어진 직사각형에서 꼭지점에 쓰여있는 수가 모두 같은 가장 큰 정사각형을 찾는 문제

단순하게 생각하면 할수록 어렵지않고 쉽게 접근할 수 있던 문제

내가 푼 정답 코드

import sys
N, M = map(int, sys.stdin.readline().split())
square = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
move = [[1,0], [1,1], [0,1]] # 모서리를 찾아주자
max_square = 1 # 최소 정사각형의 크기
for i in range(N):
    for j in range(M):
        for k in range(1,N):
            cnt = 0 # 횟수 체크
            temp = square[i][j] #시작 꼭지점 체크
            for dy, dx in move : # 한 꼭지점에 대해
                ny, nx = i + dy*k, j + dx*k # 정사각형 늘려가면서 꼭지점만 체크
                if 0 <= ny < N and 0 <= nx < M: #범위를 벗어나지 않는 선에서
                    if square[ny][nx] == temp: #만약 다른 꼭지점이 같다면
                        cnt += 1 # 횟수 카운트
            if cnt == 3: # 만약 꼭지점의 값이 전부 같다면
                max_square = max(max_square,(k+1)*(k+1)) #최대값 비교해서 저장
print(max_square)

반응형

 

📌문제 접근 포인트

1. 문제의 요구 조건은 최대 정사각형이므로 한 지점을 정했으면, 그 점을 기준으로 나머지 3개의 꼭지점만 고려
2. 선택한 지점에서 → 방향의 꼭지점, ↓ 방향의 꼭지점, ↘ 방향의 꼭지점만 고려해주면 모든 영역을 탐색할 수 있게 되므로 방향을 위한 move를 정의
3. 선택한 지점 값을 기억해서, 정사각형 모양 방향으로 for문을 활용하여 넓혀서 탐색
4. 탐색한 지점의 값이 3에서 기억한 값과 같다면, 횟수를 체크
5. 체크한 횟수가 3이 된다면, 정사각형을 이룰 수 있는 것이고 그 때의 정사각형의 넓이를 구하기
6. 위 방법으로 체크시 2*2 이상의 정사각형만 체크가 가능하므로, 만약 2*2 이상의 정사각형이 존재하지 않을 경우에는 1칸의 넓이인 1을 출력할 수 있도록 최초 값을 1로 설정

---

느낀 점

전형적인 구현, 브루트포스 문제였다. 처음 접근 할 때 항상 백준의 시간초과와 메모리 초과를 마주쳐서 그런가 위처럼 완전 탐색을 하면서도, 다른 줄일 수 있는 방법부터 생각하려고 했다.

3가지 꼭지점을 찾을 때도, 값을 리스트로 따로 만들까 했는데 이러면 메모리를 잡아먹으니 비효율적이되니 숫자만 체크해주는 식으로 구현하자하였고(과거의 나였으면 리스트로 저장했을 것) 그냥 요구조건대로 최대한 고려하고자 단순하게 생각하였다. 사실 범위 내에서를 고려해주는것도 0보다 작아질일 없으니 if 문의 0 <=ny < N 부분도 0<=을 뺏어도 괜찮았을거 같고, 마지막 줄에 대해서는 어차피 존재하지 않을테니 마지막 줄은 뺸다거나 그런 식으로 해서 탐색양을 조금 줄였어도 괜찮았을거란 생각이 다 풀고나서 들었다.

점점 너무 복잡하지 않게, 요구조건을 최대한 단순하게 있는 그대로 풀어나가려는 시도를 하면서 성공할 때 마다 코딩 기술이 늘어난거 같은 느낌을 받아서 좋았다.