(Python/🥈3)백준 알고리즘 1051번 : 숫자 정사각형

 

문제 바로가기 

숫자 정사각형

 

문제:

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력:

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력:

첫째 줄에 정답 정사각형의 크기를 출력한다.

 

풀이:

 

파이썬

n, m = map(int, sys.stdin.readline().split(" "))
graph = [list(map(int, input())) for _ in range(n)]
result = 0
# 정사각형 크기
for k in range(n + 1):
    # x 좌표
    for x in range(n):
        # y좌표
        for y in range(m):
            if x+k < n and y + k < m and graph[x][y] == graph[x][y + k] == graph[x + k][y] == graph[x + k][y + k]:
                result = max((k + 1) ** 2, result)
print(result)

 

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class java_1051_숫자정사각형 {
    static int n,m;
    static int result = (int) -1e9;
    static int[][] graph;
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

        graph = new int[n][m];
        System.out.println(Arrays.deepToString(graph));
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(bf.readLine());
            String row = stk.nextToken();
            for (int j = 0; j < m; j++) {
                graph[i][j] = Character.getNumericValue(row.charAt(j));
            }
        }
        for (int k = 0; k < n + 1; k++) {

            for (int x = 0; x < n; x++) {

                for (int y = 0; y < m; y++) {
                    if (x + k < n && y + k < m && graph[x][y] == graph[x][y + k] && graph[x][y] == graph[x + k][y] && graph[x][y] == graph[x + k][y + k]) {
                        result = Math.max(result, (k + 1) * (k + 1));
                    }
                }
            }
        }
        System.out.println(result);
    }
}

 

k는 정사각형의 한변의 길이 x = x좌표 y=y 좌표

네 꼭짓점 하나하나 체크해준다.