백준1051 - 숫자 정사각형

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

1051번: 숫자 정사각형

삼중포문을 돌려서 풀었다. 범위가 작아서 시간초과가 날 고민하지 않았다. 플루이드 와샬 알고리즘과 비슷하게 구현하엿다. 맨 바깥 포문을 한 변의 길이로 잡고 한 변의 길이를 기준으로 나머지 두개의 포문을 돌렸다. 구현만 할 줄 알면 어려운 알고리즘 필요없이 풀 수 있는 문제였다.

 

#include <iostream>
#include <string>
using namespace std;

int main() {
	int n, m; //n은 세로, m은 가로
	int ans;
	int length; //n과 m중 긴 변의 길이
	char mat[50][50]; //숫자를 담을 공간

	//땅에 정보를 입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mat[i][j];
		}
	}

	if (n < m) { //가로로 긴 경우
		length = n - 1; //인덱스가 기준이기 때문에 -1을 해준다.
		
	}
	else { //세로로 긴 경우
		length = m - 1; //인덱스가 기준이기 때문에 -1을 해준다.
		
	}

	//한 변의 길이를 기준으로 모든 구역을 탐색한다.
	for (int k = 0; k <= length; k++) {
		bool check = false; //flag 변수
		for (int i = 0; i < n - k; i++) { //길이가 k인 경우 세로는 n - k - 1 까지만 탐색을 한다.
			for (int j = 0; j < m - k; j++) { //길이가 k인 경우 가로는 n - k - 1 까지만 탐색을 한다.
				if (mat[i][j] == mat[i][j + k] && mat[i][j] == mat[i + k][j] && mat[i][j] == mat[i + k][j + k]) { //모든 꼭지점의 숫자가 같으면
					ans = k + 1; //인덱스에서 +1을 하면 길이가 된다.
					check = true; //flag변수를 true변환
					break; //탈출
				}
			}
			if (check) { //flag변수가 true면
				break; //탈출
			}
		}
	}

	cout << ans * ans; //최대 면적을 구한다.
	
}