[Algorithm] 99클럽 코테 스터디 12일차 TIL | 백준_숫자 정사각형(1051번)

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

---

반례를 찾느라 진빠졌던 문제다;

완전탐색이라고 생각하고 풀면 어렵지 않다.

 

왼쪽 위 부터 오른쪽 아래까지 모두 검사하며 정사각형을 구한다.

배열로 치면

arr[0][0]~arr[N-1][M-1] 까지

 

만약 세로줄에서 같은 수를 찾았다면 가로줄에서 같은 값이 있는지 찾는다.

이렇게 총 4개의 점에 대해 검사를 해야한다.

public static int rectangle(int a, int b){
    int n = arr[a][b];
    int h,w;
    int area = 0;

    for(int i = a+1; i < N; i++){
        if(arr[i][b] == n){
            h = i-a+1;
            for(int j = b+1; j < M; j++){
                if(arr[a][j] == n && arr[i][j] == n){
                    w = j-b+1;
                    if(h==w){
                        area = Math.max(area, h*w);
                    }
                }
            }
        }
    }
    return area;
}

arr[i][j] == n 부분을 빼먹고 맞는데 왜 틀리지? 라고 생각했으나

역시 컴퓨터는 나보다 정확하다

내가 놓친 반례는 아래의 경우의 수다.

3 3
222
223
223

 

전체코드

import java.util.*;
import java.io.*;
class Main{
    static int N,M;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < M; j++){
                arr[i][j] = str.charAt(j) - '0';
            }
        }
        int max = 1;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                max = Math.max(max, rectangle(i,j));
            }
        }
        System.out.println(max);
    }
    public static int rectangle(int a, int b){
        int n = arr[a][b];
        int h,w;
        int area = 0;

        for(int i = a+1; i < N; i++){
            if(arr[i][b] == n){
                h = i-a+1;
                for(int j = b+1; j < M; j++){
                    if(arr[a][j] == n && arr[i][j] == n){
                        w = j-b+1;
                        if(h==w){
                            area = Math.max(area, h*w);
                        }
                    }
                }
            }
        }
        return area;
    }
}