백준 #1051 숫자 정사각형

문제 자체는 상당히 간단합니다.  난이도도 Silver III로 크게 어렵지 않은 문제입니다.  정답비율은 37%정도로 낮은 편이네요.

 

NxM 의 숫자 행렬이 주어지는데, 이 중에 정사각형을 이룰 수 있는 4개의 숫자를 골라야 하는데, 행과 열에 평행하면서 4개의 숫자가 같은 숫자여야 합니다.  가장 작은 경우는 1x1 정사각형이 될겁니다.

 

아래는 실제 문제의 링크입니다.

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

1051번: 숫자 정사각형

 

전 단순무식한 방법으로 문제를 풀었습니다.  N과 M 중에 작은값을 선택한 후에, 숫자를 하나씩 줄여가면서 조건에 맞는 숫자 4개가 존재하는지를 검사합니다.  그래서 조건에 맞는 숫자를 찾으면, 그 상태에서 결과를 출력합니다.

 

제가 짠 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1051 - Number Square
//    - by Aubrey Choi
//    - created at 2019-07-01
//----------------------------------------------------------------------------------------
#include <stdio.h>

bool search(char map[][51], int n, int m, int sq)
{
  for(int i = 0; i < n-sq; i++) for(int j = 0; j < m-sq; j++)
  {
    char s = map[i][j];
    if(s==map[i][j+sq] && s==map[i+sq][j] && s==map[i+sq][j+sq]) return true;
  }
  return false;
}

int main()
{
  char map[50][51];
  int n, m, sq;
  scanf("%d%d", &n, &m);
  sq = n<m?n:m;
  for(int i = 0; i < n; i++) scanf("%s", map[i]);
  while(sq-- && !search(map, n, m, sq));
  printf("%d\n", (sq+1)*(sq+1));
}