/ BOJ

BOJ_1051_숫자정사각형_JAVA

문제 : 숫자정사각형

링크 : BOJ_1051_숫자정사각형

접근 방식

간단하게 완전탐색으로 풀 수 있는 문제였다.

문제의 입력으로 주어지는 범위는 1~50, 즉 각 배열의 칸마다 최대로 탐색을 진행해도 50x50x50으로, N^3의 시간복잡도를 가지고있지만 그 실제 범위가 매우 좁다.

따라서 완전탐색을 하며, 같은 숫자로 이루어져있는 가장 큰 정사각형의 넓이를 찾아 출력해주었다.

소스 코드

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

public class BOJ_1051_숫자정사각형 {
	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st= new StringTokenizer(in.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		char[][] arr = new char[N][M];

		for(int i=0;i<N;i++) {
			arr[i] = in.readLine().toCharArray();
		}

		int answer =1;

		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				int cur = arr[i][j];

				for(int d=1;d<50;d++) {
					if(i+d >= N || j+d >= M) {
						break;
					}
					// 4개 범위가 같은 수라면
					if(arr[i][j] == cur && arr[i+d][j] == cur &&
							arr[i][j+d] ==cur && arr[i+d][j+d] == cur) {
						answer = Math.max(answer, (d+1) * (d+1));
					}
				}

			}
		}

		System.out.println(answer);

	}
}

나는 한 번에 코드를 짜고, 그 코드가 들어맞을 때 희열을 느끼는 편인데, 쉬운 문제였지만 오랜만에 한 번에 코드를 짜고 맞춘 문제라서 기분이 좋았다.