반응형
https://www.acmicpc.net/problem/1051
1051번: 숫자 정사각형
N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행
www.acmicpc.net
💡 숫자 정사각형
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의 한 문자를 위 메서드 쓸 수 없는 이유는 인자 형태가 맞지 않아서이다.
반응형
'CO-TE > 백준' 카테고리의 다른 글
| [백준] 1010번 C++ "다리 놓기" 풀이 / 조합 (0) | 2023.11.20 |
|---|---|
| [백준] 1806번 C++ "부분합" 풀이 / 투 포인터-부분합 (1) | 2023.11.19 |
| [백준] 1032번 C++ "명령 프롬프트" 풀이 / 구현 문제 (0) | 2023.11.19 |
| [백준] C++ 1158번 "요세푸스 문제" 풀이 / 자료구조 문제 (1) | 2023.11.18 |
| [백준] 9935번 JAVA 골드4 "문자열 폭발" (0) | 2023.11.03 |
