[Baekjoon] 1051_숫자 정사각형

Silver III

문제(출처: https://www.acmicpc.net/problem/1051)

---

< 숫자 정사각형 >

 

문제 풀이 

 

가능한 정사각형 크기만큼 꼭짓점을 살펴본다.

 

 my solution (Java)

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

public class _1051_ { // 숫자 정사각형

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.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 str = bf.readLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}

		int result = 1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int size = 1;
				while (i + size < n && j + size < m) {

					if (arr[i][j] == arr[i + size][j] && arr[i][j] == arr[i][j + size]
							&& arr[i][j] == arr[i + size][j + size]) {
						result = Math.max(result, size + 1);
					}
					size += 1;
				}
			}
		}
		System.out.println(result * result);
	}
}

변수)
n, m : 직사각형 크기
arr : 직사각형에 쓰여있는 수
result : 가장 큰 정사각형 한 변의 길이
size : 현재 정사각형 한 변의 길이

 

직사각형 크기를 입력받는다. 직사각형에 쓰여있는 수를 입력받아 arr에 저장한다. 직사각형을 전체 탐색하면서 정사각형을 만들 때 꼭짓점에 쓰여 있는 수가 모두 같은지 판단하여 만들 수 있는 가장 큰 정사각형의 길이를 찾는다.

 

최종 정사각형 크기인 result*result를 출력한다. 

---

---