백준 1051번 <숫자 정사각형>

백준 알고리즘 1051번

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

1051번: 숫자 정사각형

---

1051번

n*m 크기의 직사각형이 있다. 각 칸에 한 자리 숫자가 적혀있을 때, 이 직사각형 안에서 가장 큰 정사각형의 크기를 찾아라. 이때 정사각형은 각 꼭짓점에 쓰여있는 수가 모두 같아야 한다.

 

입력으로 첫 줄에 n과 m이 주어진다. 그 다음 n줄에 걸쳐 직사각형에 대한 정보가 주어진다.

 

출력으로 해당 직사각형에서 가장 큰 정사각형의 크기를 구해서 출력하면 된다.

---

문제 해결

한 변의 길이가 1인 정사각형부터 점점 길이를 1씩 늘려가면서 정사각형이 만들어지는지 확인하는 방법으로 구할 수 있다.

한 변의 길이가 가장 긴 정사각형을 찾으면 답을 구할 수 있다.

 

정사각형의 왼쪽 위 꼭짓점을 기준으로 생각해보자.

위의 그림은 한 변의 길이가 k인 정사각형을 왼쪽 위 꼭짓점을 (i, j)라고 했을 때, 다른 꼭짓점의 좌표를 나타내고 있다.

정사각형을 이루기 위한 조건으로 (i, j), (i, j+k), (i+k, j), (i+k, j+k) 의 값이 모두 같은지 확인하면 된다.

(당연히 i+k와 j+k가 범위를 벗어나지 않아야 한다.)

---

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");
		int n = Integer.parseInt(inArr[0]);
		int m = Integer.parseInt(inArr[1]);
		int[][] map = new int[n][m];
		for (int i = 0; i < n; i++) {
			String temp = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = (int) (temp.charAt(j) - '0');
			}
		}
		int max = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int len = 1;
				int nx = i + len;
				int ny = j + len;
				while (true) {

					if (nx >= n || ny >= m) {
						break;
					}
					if (map[i][j] == map[nx][j] && map[nx][j] == map[i][ny] && map[i][ny] == map[nx][ny]) {
						max = Math.max(max, len + 1);
					}
					len++;
					nx = i + len;
					ny = j + len;

				}
			}
		}
		System.out.println(max * max);
	}

}

---

결과

 

---