백준 1051번 숫자 정사각형 파이썬 풀이

🔷 백준 1051번 숫자 정사각형 파이썬 풀이

✅ 문제

N×M 크기의 직사각형 격자 안에 한 자리 숫자가 적혀 있습니다. 이 격자에서 네 꼭짓점에 적힌 숫자가 모두 같은 가장 큰 정사각형을 찾고, 그 넓이를 구하는 문제입니다. 정사각형은 반드시 행과 열에 평행하게만 만들어야 합니다.

✅ 입력

• 첫째 줄: N, M (1 ≤ N,M ≤ 50)
• 둘째 줄부터 N개의 줄: 길이 M의 숫자가 공백 없이 주어짐

✅ 출력

네 꼭짓점이 모두 같은 가장 큰 정사각형의 넓이

✅ 예제 입력

42101
22100
22101
    

✅ 예제 출력

9
    

✅ 아이디어

이 문제를 해결하기 위해 i,j로 격자 안을 옮겨가며 탐색하고, k를 늘려가며 정사각형의 크기를 키워 탐색하는 방식을 사용합니다. 즉, i,j로 “위치”를 옮기고, k로 “크기”를 키우며 탐색하는 이중 구조입니다.

✅ 1️⃣ i,j로 현재 정사각형 위치를 옮겨가며 탐색

가장 작은 정사각형인 2×2(즉, k=1)부터 시작합니다. i,j는 왼쪽 위 꼭짓점의 좌표입니다. i,j를 격자 안에서 가능한 모든 위치로 옮겨가며, 현재 크기의 정사각형이 가능한지 확인합니다.

예를 들어, k=1(2×2)일 때는 아래처럼 i,j가 옮겨 다니며 탐색합니다.

왼쪽 위 첫 번째 위치:

[4 2] 1 0 1
[2 2] 1 0 0
 2 2 1 0 1
    

오른쪽으로 한 칸 이동:

4 [2 1] 0 1
2 [2 1] 0 0
2 2 1 0 1
    

다시 오른쪽으로 이동:

4 2 [1 0] 1
2 2 [1 0] 0
2 2 1 0 1
    

한 행을 끝까지 탐색한 뒤, i를 한 칸 내려 다시 왼쪽부터 탐색합니다:

 4 2 1 0 1
[2 2] 1 0 0
[2 2] 1 0 1
    

다시 오른쪽으로 옮깁니다:

 4 2 1 0 1
2 [2 1] 0 0
2 [2 1] 0 1
    

✅ 2️⃣ k를 증가시켜 크기를 키우며 탐색

k=1(2×2)로 격자 전체를 탐색한 후, k=2(3×3)로 크기를 키웁니다. k가 증가할수록 정사각형의 크기가 커지고, 탐색 가능한 i,j의 범위는 줄어듭니다. k=2(3×3)일 때도 같은 방식으로 i,j를 옮겨가며 탐색합니다.

왼쪽 위 첫 번째 위치:

[4 2 1] 0 1
[2 2 1] 0 0
[2 2 1] 0 1
    

i,j를 오른쪽으로 옮깁니다:

4 [2 1 0] 1
2 [2 1 0] 0
2 [2 1 0] 1
    

이처럼 k를 1씩 늘려가며 더 큰 정사각형을 시도합니다. 더 이상 네 꼭짓점이 모두 같은 정사각형이 없으면 그 전 크기가 최대 크기입니다.

✅ 3️⃣ 네 꼭짓점이 같은지 확인

각각의 i,j와 k가 정해졌을 때, 해당 정사각형의 꼭짓점 네 칸이 모두 같은지를 검사합니다. 꼭짓점 좌표는 다음과 같습니다:

• 왼쪽 위: (i,j)
• 오른쪽 위: (i,j+k)
• 왼쪽 아래: (i+k,j)
• 오른쪽 아래: (i+k,j+k)

예를 들어, k=1일 때 다음 위치는 네 꼭짓점이 같아 유효합니다:

[2 2] 1 0 1
[2 2] 1 0 0
 2 2 1 0 1
    

네, 정말 옳으신 지적입니다. 말씀하신 대로 단순히 “코드 읽기”가 아니라, 그 코드가 실제로 탐색하는 모습과 대응되는 상황을 텍스트 다이어그램으로 보여주며 직관적으로 설명해야 한다는 뜻입니다. 이제 제대로 작성하겠습니다.

✅ 전체 코드

N, M = map(int, input().split())
grid = []
for _ in range(N):
    grid.append(list(map(int, list(input().strip()))))

max_k = 0
min_n = min(N, M)

for k in range(min_n):
    for i in range(N - k):
        for j in range(M - k):
            if (grid[i][j] == grid[i][j+k] and
                grid[i][j] == grid[i+k][j] and
                grid[i][j] == grid[i+k][j+k]):
                max_k = max(max_k, k)

print((max_k + 1) * (max_k + 1))
    

✅ 개별 코드 설명 (아이디어 + 다이어그램)

🔷 1️⃣ 입력 처리 및 배열 초기화

N, M = map(int, input().split())
grid = []
for _ in range(N):
    grid.append(list(map(int, list(input().strip()))))
    

📌 아이디어: 첫 줄에서 N과 M을 입력받고, 각 줄을 문자열로 받아서 리스트로 변환합니다. 즉, 이렇게 생긴 입력을:

42101
22100
22101
    

다음과 같은 2차원 리스트에 채웁니다:

[[4, 2, 1, 0, 1],
 [2, 2, 1, 0, 0],
 [2, 2, 1, 0, 1]]
    

🔷 2️⃣ 최대 크기 후보 계산

min_n = min(N, M)
    

📌 아이디어: 가장 큰 정사각형은 격자의 작은 쪽 길이를 넘지 못합니다. 예를 들어 3×5 격자에서는 최대 3×3 정사각형까지만 가능합니다.

🔷 3️⃣ k와 i,j를 늘리며 탐색

for k in range(min_n):
    for i in range(N - k):
        for j in range(M - k):
            if (grid[i][j] == grid[i][j+k] and
                grid[i][j] == grid[i+k][j] and
                grid[i][j] == grid[i+k][j+k]):
                max_k = max(max_k, k)
    

📌 아이디어:

• k는 현재 정사각형의 크기(k+1)입니다.
• i,j는 왼쪽 위 꼭짓점입니다.
• 격자 안에서 정사각형이 오른쪽, 아래로 벗어나지 않는 범위에서만 탐색합니다.

📌 실제 탐색 예시: k=1(2×2)일 때 (i=0,j=0) 기준으로 탐색하면:

[4 2] 1 0 1
[2 2] 1 0 0
 2 2 1 0 1
    

j를 한 칸 오른쪽으로 옮기면:

4 [2 1] 0 1
2 [2 1] 0 0
2 2 1 0 1
    

j를 끝까지 다 옮기고 나면 i를 한 칸 아래로 내려가고 다시 j를 왼쪽부터 탐색합니다:

 4 2 1 0 1
[2 2] 1 0 0
[2 2] 1 0 1
    

k를 증가시켜 k=2(3×3)로 탐색할 때는 다음처럼 더 큰 범위를 검사합니다:

[4 2 1] 0 1
[2 2 1] 0 0
[2 2 1] 0 1
    

이처럼 k가 커질수록 정사각형이 커지고, i,j의 탐색 범위는 좁아집니다.

🔷 4️⃣ 넓이 계산 및 출력

print((max_k + 1) * (max_k + 1))
    

📌 아이디어: max_k TTS(1) k+1은 찾은 가장 큰 정사각형의 한 변의 길이입니다. 넓이는 길이×길이입니다.

✅ 결론

• 격자 전체를 i,j로 옮겨가며 현재 크기의 정사각형을 탐색합니다.
• k를 늘리며 정사각형의 크기를 키워가며 탐색합니다.
• 네 꼭짓점이 모두 같은지를 비교해 유효성을 확인합니다.
• 가장 큰 정사각형의 넓이를 출력합니다.