뚝딱뚝딱

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

💡 숫자 정사각형

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

예제 입력

3 5
42101
22100
22101

출력

9

✅ 문제 풀이

주어진 행렬에서 가능한 모든 정사각형을 구해야 함을 알 수 있다. 따라서 이 문제는 무식하게 다 접근하는 브루트포스 알고리즘을 이용해야 한다.

• 먼저 입력의 형태를 보자. 입력으로 들어오는 행렬 값이 공백으로 구분되어 있지않고 붙어있다.
  => 따라서 string으로 받고, 한 문자씩 잘라서 숫자로 바꾸어준 후 벡터에 값을 반영할 것이다.
• 벡터가 다 채워졌으면, 이제 왼쪽 상단 꼭지점을 기준으로, 배열을 순회할 것이다.
  => 무슨말이냐 하면, 배열의 각 점을 정사각형의 왼쪽 상단 꼭지점으로 생각하고, 정사각형을 찾아보는 것이다.
• 그런데, 입력을 받을 때 행과 열의 크기를 받았다. 정사각형은 가로와 세로의 길이가 같아야 하기 때문에 행과 열 중에서 더 작은 값이 정사각형의 최대 길이가 될 수 있다.
• 따라서 행과 열 중 최소의 길이가 1이었다면, 최대 정사각형 길이는 1이기 때문에 크기가 1이다. 
• 그리고 행과 열 중 최소의 길이가 1이 아니라면 그 값을 m에 저장해 두고, 다음 절차를 통해 최대 길이를 찾아낼 수 있다.
• 먼저 정사각형의 한변의 길이가 2인 것부터 찾아볼 것이다.
• 현재 왼쪽 상단 꼭지점의 위치를 (i,j)라고 할 때 길이가 2인 정사각형의 꼭짓점은 (i+1, j) (i,j+1), (i+1, j+1)이 된다.
• 따라서 k가 1일 때부터 m보다 작을 때까지 정사각형을 키워가면서 조건을 만족하는지 보면 된다.
• i+k<N이고, j+k<M이면, 해당 정사각형은 행렬안에 유효한 것이다. 따라서 이런 경우에는 (i,j)가 (i+1, j) (i,j+1), (i+1, j+1)각각과 값이 동일한지 비교해주면 된다. 
  => 값이 동일하면, answer의 기존 값과 비교해서 더 큰 값으로 answer를 갱신해주면된다.
• 참고로 answer는 행렬을 순회하기 전에 1로 초기화 하여 생성해두어야 한다.
• 모든 순회가 끝난 후 최종 answer값을 제곱한 값을 출력해주면 된다. (문제에서 정사각형의 크기를반환하라고 하였기 때문이다.)

전체 코드는 아래와 같다.

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	int m = min(N, M);//작은 값이 정사각형의 한 변의 max가 됨

	vector<vector<int>> rec(N, vector<int>(M, 0));

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;

		for (int j = 0; j < str.length(); j++) {
			rec[i][j] = str[j]-'0'; //char 문자를 숫자로 바꾸는 함수는 atoi를 쓰지만, string으로 되어 있는 경우엔 인자가 맞지 않으므로,'0'을 뻬주어서 구한다.
		}
	}

	if (m == 1) {
		cout << 1;
		return 0;
	}

	int answer = 1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int k = 1; k < m; k++) {
				if (i + k < N && j + k < M) {//사각형이 범위에 들어오는지 확인
					int t = rec[i][j];//기준이 되는 값을 저장
					if (rec[i][j + k] == t && rec[i + k][j] == t && rec[i + k][j + k] == t) {
						answer = max(k + 1, answer);
					}
				}
			}
		}
	}

	cout << answer * answer;//크기는 변의 제곱

	return 0;
}

✏ c++ 문법 알고 넘어가기!

• 2차원 벡터 선언하기 : vector<vector<int>> vec(행크기, vector<int>(열크기, 초기값));
• string의 각 문자를 숫자로 변환 : string의 각 문자를 변환할 때는 그냥 str[i]-'0'을 해주면 숫자 값을 얻을 수 있다.
  만약 char로 선언된 문자라면, atoi(문자) 메서드를 사용하면 된다.
  => string의 한 문자를 위 메서드 쓸 수 없는 이유는 인자 형태가 맞지 않아서이다.