[백준 1051] 숫자 정사각형 (S3)

📍 문제

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

📍 문제 풀이

이중 for문을 통해서 배열을 돌면서 size를 줄이는 식으로 진행했다. 

우선 정사각형의 최대 길이는 `n,m`값 중 더 작은 값일 것이다. 이 값을 `size`로 두고 시작한다.

 

이 문제에서 주의해야하는 점은 `size`에 따라서 확인해야하는 배열의 값이었다.

 

예를 들어, 아래의 경우와 같이 `i,j,size`가 각각 0,0,3인 경우를 생각해보자.

`size`가 3이라고 maps[0][3], maps[3][0], maps[3][3]을 확인하는게 아니라

maps[0][2], maps[2][0], maps[2][2]를 확인해야 `size`가 3인 정사각형을 만들 수 있다.

이 점을 주의하면서 확인하는 인덱스의 범위와 값들을 조건에 맞는지 확인하면된다. 

 

`size`를 점차 줄여가면서 만족하는 정사각형이 있는 경우 정사각형의 사이즈를 출력하고 종료한다.

종료할 수 있는 이유는 `size`를 감소시키며 코드를 진행해 가장 먼저 만족하는 값이 최대값이기 때문이다. 

만약 증가하는 방향으로 코드를 진행했다면, 매번 최대값인지 확인하는 과정이 필요하다.

 

📍전체 코드 (Java)

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

public class Main {
	static int n, m;
	static int[][] maps;

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		// 배열 초기화
		maps = new int[n][m];
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < m; j++) {
				maps[i][j] = str.charAt(j) - '0';
			}
		}

		int size = Math.min(n, m);
		while (size > 1) {
			for (int i = 0; i <= n - size; i++) {
				for (int j = 0; j <= m - size; j++) {
					if (chkValue(i, j, size)) {
						// 조건에 만족하는 정사각형을 찾았다면 -> 최대값
						System.out.println(size * size);
						return;
					}
				}
			}
            // 해당 size에 대해서 만족하는 정사각형이 없는 경우
			size--;
		}
		System.out.println(size * size);
	}

	private static boolean chkValue(int x, int y, int size) {
		if (x + size - 1 < n && y + size - 1 < m) {
			int v1 = maps[x][y];
			int v2 = maps[x + size - 1][y];
			int v3 = maps[x][y + size - 1];
			int v4 = maps[x + size - 1][y + size - 1];

			if (v1 == v2 && v1 == v3 && v1 == v4) {
				return true;
			}
		}
		return false;
	}
}