[BaekJoon] 1051 숫자 정사각형

1.  문제 링크

2.  문제

요약

• 각 칸에 한 자리 숫자가 적혀있는 N * M 크기의 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 문제입니다.
• 입력: 첫번째 줄에는 N과 M이 주어지고 그 다음 줄부터 N개의 줄에는 M만큼의 길이의 숫자가 주어집니다.
• 출력: 가장 큰 정사각형의 크기를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public int findSquare(int[] size, ArrayList<String> rectangle) {
		if(size[0] == 1 || size[1] == 1) {
			return 1;
		}
		int count;
		if(size[0] > size[1]) {
			count = size[1];
		} else {
			count = size[0];
		}
		while(true) {
			for(int i = 0; i <= size[0] - count; i++) {
				for(int j = 0; j <= size[1] - count; j++) {
					if(Integer.parseInt(rectangle.get(i).substring(j, j + 1)) == Integer.parseInt(rectangle.get(i).substring(j + (count - 1), j + count))
							&& Integer.parseInt(rectangle.get(i).substring(j, j + 1)) == Integer.parseInt(rectangle.get(i + (count - 1)).substring(j + (count - 1), j + count))
							&& Integer.parseInt(rectangle.get(i).substring(j, j + 1)) == Integer.parseInt(rectangle.get(i + (count - 1)).substring(j, j + 1))) {
						return count * count;
					}
				}
			}
			count--;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String size_str = br.readLine();
		StringTokenizer st = new StringTokenizer(size_str);
		int[] size = new int[2];
		size[0] = Integer.parseInt(st.nextToken());
		size[1] = Integer.parseInt(st.nextToken());
		ArrayList<String> rectangle = new ArrayList<String>();
		for(int i = 0; i < size[0]; i++) {
			rectangle.add(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.findSquare(size, rectangle) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 만약 크기에 해당하는 N 또는 M 둘 중 하나가 1이라면 1보다 더 큰 정사각형을 만들 수 없으므로 이 때는 1이 가장 큰 정사각형의 크기가 될 것입니다.
• 가장 큰 정사각형을 찾기 위해 현재 주어진 크기에서 만들 수 있는 가장 큰 정사각형부터 크기를 하나씩 줄여가면서 정사각형이 만들어지는 순간을 찾습니다.
• 찾을 때는, 횡으로 또는 열로 찾는 방법이 있을텐데 저는 횡으로 찾는 방법을 택했습니다.
• 각 꼭짓점의 값이 같은 정사각형을 찾아야하므로 정사각형의 한 변의 길이를 이용하여 각 꼭짓점을 찾고 정사각형이 형성될 때까지 한 변의 길이를 하나씩 줄여가며 찾습니다.
• 정사각형이 형성됐을 때, 해당 한 변의 길이를 제곱하면 해당 정사각형의 크기를 찾을 수 있고 이 크기가 가장 큰 정사각형의 크기가 됩니다.