[Python/Java] 백준 1051 - 숫자 정사각형 [Brute Force]

문제

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

 

해설

Brute Force를 이용하여 모든 경우의 수를 탐색하여 해결하였다. CNN에서의 Sliding Window를 연상해보면 더 쉽게 해결할 수 있다.

 

Python

from sys import stdin


def brute_force(matrix: list, n: int, m: int):
    max_size = n if n < m else m

    result = []
    for i in range(n):
        for j in range(m):
            for k in range(max_size):
                if i + k < n and j + k < m:
                    if matrix[i][j] == matrix[i + k][j] == matrix[i][j + k] == matrix[i + k][j + k]:
                        result.append((k + 1) ** 2)
    print(max(result))


n, m = map(int, stdin.readline().split(" "))
matrix = [list(stdin.readline().strip()) for _ in range(n)]
brute_force(matrix, n, m)

 

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] condition = br.readLine().split(" ");
        int n = Integer.parseInt(condition[0]);
        int m = Integer.parseInt(condition[1]);

        int[][] matrix = new int[n][m];

        for(int i = 0; i < n; i++) {
            String[] rows = br.readLine().split("");
            for(int j = 0; j < rows.length; j++) {
                matrix[i][j] = Integer.parseInt(rows[j]);
            }
        }

        sb.append(bruteForce(matrix, n, m));
        System.out.println(sb);
    }

    public static int bruteForce(int[][] matrix, int n, int m) {
        List<Integer> result = new ArrayList<>();

        int maxSize;
        if(n<m){ maxSize = n; }
        else{ maxSize = m; }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                for(int k=0; k<maxSize; k++){
                    if((i+k < n) && (j+k < m)){
                        if((matrix[i][j] == matrix[i+k][j])
                                && (matrix[i+k][j]) == (matrix[i][j+k])
                                && (matrix[i][j+k] == matrix[i+k][j+k])){
                            result.add((k+1)*(k+1));
                        }
                    }
                }
            }            
        }

        return Collections.max(result);
    }
}