[완전탐색] 백준 1051 숫자 정사각형 풀이

문제

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

입력

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

출력

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

 

---

 

풀이

1. (a, b) 좌표 정보를 담고 있는 Node 클래스를 생성한다.

2. 입력받은 배열의 가로길이와 세로길이중 더 작은 것을 min에 저장한다.

3. process 함수를 통해서 재귀를 실시한다.

4. size (정사각형 크기)가 min이랑 같을 경우 종료한다.

5. 만약 4개의 꼭짓점의 값이 같다면 값을 저장하여 저장한다.

 

코드(JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Node {
    int a, b;

    Node(int a, int b) {
        this.a = a;
        this.b = b;
    }

    public void setA(int a) {
        this.a = a;
    }

    public void setB(int b) {
        this.b = b;
    }
}

public class Main {
    static int answer = 1;
    static int min = 0;
    static int[][] arr;
    static int x_length;
    static int y_length;

    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String input = bf.readLine();
        String inputs[] = input.split(" ");
        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);
        arr = new int[n][m];
        x_length = arr[0].length;
        y_length = arr.length;
        inputs = new String[n];

        for (int i = 0; i < n; i++) {
            inputs[i] = bf.readLine();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = inputs[i].charAt(j);
            }
        }
        // max 값 구하기
        if(x_length <= y_length){
            min = x_length;
        }else{
            min = y_length;
        }
        Node node = new Node(0, 0);
        process(node, 1);
        System.out.println(answer);
    }

    // int a, b 시작 점
    public static void process(Node node, int size) {
        if (min <= size) {
            return;
        }
        int a = node.a;
        int b = node.b;
        int x = a + size;
        int y = b + size;
        if (x == x_length) {
            node.setA(0);
            node.setB(++b);
            process(node, size);
            return;
        }
        if (y == y_length) {
            size++;
            node.setA(0);
            node.setB(0);
            process(node, size);
            return;
        }
        // 4개의 꼭짓점이 같다면 값 구하기
        if (arr[b][a] == arr[b][x] && arr[b][x] == arr[y][a] && arr[y][a] == arr[y][x]) {
            answer = (size + 1) * (size + 1);
        }
        node.setA(++a);
        process(node, size);
    }
}