백준_1051 숫자 정사각형(자바) / 브루드 포스 알고리즘

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_1051 {
	public static void main(String[] args) throws IOException {
		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 temp = br.readLine();
			for (int j = 0; j < M; j++) {
				arr[i][j]=temp.charAt(j)-'0';
			}
		}
		
		int ans = 1;
		int size = Integer.min(N, M);
		for (int k = 2; k <= size; k++) {
			for (int i = 0; i < N-k+1; i++) {
				for (int j = 0; j < M-k+1; j++) {
					if(arr[i][j]==arr[i+k-1][j]&&arr[i][j]==arr[i][j+k-1]&&arr[i][j]==arr[i+k-1][j+k-1]) {
						if(ans<k) {
							ans = k;
						}
					}
				}
			}
		}
		System.out.println(ans*ans);
	}
}

- 이 문제는 모든 경우의 수를 다 조사하는 문제입니다.

- 이 문제는 시간 복잡도르를 생각 해볼 수 있습니다.

- 최대 길이가 50이므로 50 50 일때 size를 50으로 지정하게 됩니다. 따라서 50*50*50 이므로 시간적으로 충분할 거 같습니다.

- for문을 돌려서 각 꼭짓점 위치의 값이 같으면 ans에 값을 저장시켜줍니다.