BOJ_1051 : 숫자 정사각형

👉 문제링크

1051번: 숫자 정사각형

---

---

🔸 문제 분석 🔸

• 입력 된 n x m크기의 수 배열에서 정사각형을 그렸을때 꼭지점이 같은 수인 경우에서 가장 큰 정사각형의 너비를 출력한다.
• 정사각형 한 변의 길이를 늘려가며 배열을 탐색해야 한다.
  • 배열의 최대 크기는 50 x 50이므로 시간복잡도가 O(n^3)이라고 해도 50^3 = 125,000으로 시간은 여유있다.
  • 1자리 문자들이 공백없이 입력되므로, 구문해서 저장해야한다.
  • 배열을 순회하며 정사각형의 네 꼭지점의 값이 같은 경우의 수 중에 너비가 가장 큰 값을 찾는다.

🔸 코드 🔸

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

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int arr[][] = new int[n][m];

        for (int i = 0; i < n; i++){
            String temp[] = br.readLine().split("");
            for (int j = 0; j < m; j++){
                arr[i][j] = Integer.parseInt(temp[j]);
            }
        }
        int answer = 0;
        int min = n < m ? n:m;
        for (int l = 1; l < min; l++){
            for (int i = 0; i < n-l; i++){
                for (int j = 0; j < m-l; j++){
                    if (l>answer && arr[i][j] == arr[i+l][j] && arr[i][j] == arr[i][j+l] && arr[i][j] == arr[i+l][j+l])
                        answer = l;
                }
            }
        }
        answer++;
        System.out.println(answer*answer);
    }
}

🔸 코드 해석 🔸

• 입력되는 배열을 이중 배열 arr에 저장한다.
  • 한 자리 숫자가 공백없이 입력되므로, split("")을 통해 String 배열 temp로 변환한다.
  • temp의 원소를 하나씩 arr에 저장한다.
• (정사각형의 한 변의 길이 - 1) 인 변수 l을 1부터 (n, m중 작은 값 - 1) 까지 반복하며 값을 확인한다.

---

🔸 end 🔸

• 생각보다 간단하게 풀 수 있었다.
• 브루트 포스 알고리즘 문제여서 시간초과를 걱정했는데, n의 크기가 50밖에 안되어서 아주 여유있었다.