본문 바로가기

Hanum.

1051 숫자 정사각형 본문

카테고리 없음

1051 숫자 정사각형

Han-um 2017. 1. 23. 22:11

1051 숫자 정사각형

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


 

◆ 문제 풀이


배열을 입력받아 그 안에서 꼭지점이 같은 수인 정사각형을 찾아내는 문제입니다.

해결을 위해 다음과 같은 방법을 이용해야 합니다.

 

 

마주보는 꼭지점을 기준으로 우선 확인 후, 나머지를 비교

문제의 조건에 맞으려면, 결과적으로 네 꼭지점이 같은 수여야 합니다. 여기에서, 기준점은 마주보는 꼭지점으로 합니다.

 

비교가 끝나는 지점을 찾아야 함

반복문을 이용할 경우, 얼마나 반복을 해야 하는가가 이 문제의 핵심입니다.

이를 판단하기 위한 방법은 여러가지가 있으나, 여기에서는 가장 간단하다고 판단되는 방법으로 진행하겠습니다.

 

배열의 끝에 -1값을 넣어주고, 배열을 문자열 배열로 정의

-1은 NULL 같은 일종의 예외값입니다. 문자열 배열에서 입력받은값이 -1이 될 수 없으므로,

대각선 비교 반복문에 -1을 만나면 반복을 탈출하도록 하여 예외처리를 끝마쳤습니다.

 

예를 들어,

 

3 5
42101
22100
22101

 

의 값이 들어왔을때,  실제 배열은

 

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. 구 본철

 

Comments