문제

---

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

코드

---

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		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[] input = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(input[j]);
			}
		}

		System.out.println(solve(N, M, arr));
	}

	public static int solve(int N, int M, int[][] arr) {
		int result = 0;
		int length = 1;
		while (true) {
			if (length > N || length > M) {
				break;
			}

			for (int i = 0; i < N; i++) {
				if (i + length > N - 1) {
					break;
				}

				for (int j = 0; j < M; j++) {
					if (j + length > M - 1) {
						break;
					}

					int one = arr[i][j];
					int two = arr[i + length][j];
					int three = arr[i][j + length];
					int four = arr[i + length][j + length];

					if (one == two && one == three && one == four) {
						result = length;
					}
				}
			}
			length++;
		}
		if (result == 0) {
			return 1;
		}
		return (result + 1) * (result + 1);
	}
}

문제 이해

---

• 입력으로 주어진 N X M크기의 직사각형 내부에서 정사각형의 영역을 선택한다.
• 그렇게 선택한 정사각형들 중 꼭지점 4개의 값이 같은 정사각형의 최대 넓이를 구하는 문제이다.

풀이 방법

---

• 우선 입력 값의 범위가 N, M < 50이며 수행시간제한은 2초이다.
• 따라서 브루트포스로 문제를 해결하면 된다.
• 깊게 생각할 필요 없이 입력 직사각형 내부에서 arr[i][j], arr[i+length][j], arr[i][j+length], arr[i+length][j+length] 4개의 값이 같은 경우마다 length를 갱신해가면 된다.
• 더이상 length가 N, M의 범위 밖에 있다면 반복문을 빠져나온다.
• 만약 한번이라도 갱신됐다면, result + 1을 제곱하여 넓이를 구해야되고, 갱신이 안됐다면 1을 반환하면 된다.

핵심 포인트

---

• 브루트포스 문제의 특성상, 탐색 범위가 배열을 벗어나지 않도록 잘 조정해야 한다.
• 한칸의 넓이를 1로 보기 때문에, length가 1이상이면 길이에 1을 더해서 제곱값을 구해야 된다.

보완할 점 / 느낀 점

---

• 문제에 명시된 그대로 구현하면 되기 때문에 크게 어려운 내용은 없었다.
• 그러나, 경계조건을 잘못 계산하여 조금 해맸었는데 이런 문제의 경우 미리 경계에 대해서 정확히 계산하고 구현해야겠다. 이런걸로 디버깅을 해야한다면 시간이 너무 아깝다.

참고자료

---