1051 숫자 정사각형
https://www.acmicpc.net/problem/1051
◆ 문제 풀이
배열을 입력받아 그 안에서 꼭지점이 같은 수인 정사각형을 찾아내는 문제입니다.
해결을 위해 다음과 같은 방법을 이용해야 합니다.
■ 마주보는 꼭지점을 기준으로 우선 확인 후, 나머지를 비교
문제의 조건에 맞으려면, 결과적으로 네 꼭지점이 같은 수여야 합니다. 여기에서, 기준점은 마주보는 꼭지점으로 합니다.
■ 비교가 끝나는 지점을 찾아야 함
반복문을 이용할 경우, 얼마나 반복을 해야 하는가가 이 문제의 핵심입니다.
이를 판단하기 위한 방법은 여러가지가 있으나, 여기에서는 가장 간단하다고 판단되는 방법으로 진행하겠습니다.
■ 배열의 끝에 -1값을 넣어주고, 배열을 문자열 배열로 정의
-1은 NULL 같은 일종의 예외값입니다. 문자열 배열에서 입력받은값이 -1이 될 수 없으므로,
대각선 비교 반복문에 -1을 만나면 반복을 탈출하도록 하여 예외처리를 끝마쳤습니다.
예를 들어,
3 5
의 값이 들어왔을때, 실제 배열은
42101 -1
22100 -1
22101 -1
-1-1-1-1-1-1
과 같은 방식으로, 예외값이 둘러싸는 형태가 됩니다.
이때, 상단 오른쪽 끝의 1이 기준이 되는 반복문에서는 마주보는 꼭지점의 값이 -1이므로 바로 반복문을 탈출.
상단 왼쪽 끝의 4가 기준이 되는 반복문에서는 마주보는 꼭지점의 값이 2 1 일때까지 반복 후 -1을 만나 반복문을 탈출하게 됩니다.
■ 문자열을 한 자릿수로 입력 받기
scanf("%1d",a) 와 같은 방법으로 입력받은 숫자를 따로따로 배열에 저장할 수 있습니다.
◆ 코드
#include <iostream>
#include <stdio.h>using namespace std;
int main(){
char all[51][51]; // 배열 선언
int a, b; // 행,렬 값
int i, j;
int Max = 0;
cin >> a >> b; // 행,렬 입력// 내용 입력
for (i = 0; i < a+1; i++) {
if (i == a) {
for (j = 0; j < b + 1; j++) {
all[i][j] = -1;
}
}
else {
for (j = 0; j < b + 1; j++) {
if (j == b) {
all[i][j] = -1;
}
else {
scanf("%1d", &all[i][j]);
}
}
}
}for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
for (int k = 0; all[i+k][j+k] != -1; k++) { // 대각선으로 선탐색, -1을 만날때까지.
if (all[i][j] == all[i + k][j + k]&& all[i][j] == all[i][j + k]&& all[i][j] == all[i + k][j]) {
// 모두 값이 같으면, 현재 사이즈 Max로 저장
if (Max < k) Max = k;
}
}
}
}cout << (Max + 1)*(Max + 1);
return 0;
}
by. 구 본철