백준 1051 : 숫자 정사각형

💡기본 정보

유형
: 브루트포스
풀이 날짜
: 2025년 01월11일 
풀이방법 한줄 요약
: 전체 직사각형을 돌아다니며 똑같은 수 찾기 

 

💡문제에서 구해야 할 것

N*M 크기의 직사각형 각 칸에 한 자리 숫자가 적힘 . 

이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램
- 입력 : 첫째 줄에 N과 M이 주어짐 . N과 M은 50보다 작거나 같은 자연수
            둘째 줄부터 N개의 줄에 수가 주어짐
 출력 : 첫째 줄에 정답 정사각형의 크기를 출력함

 

💡알고리즘 설계

- N*M 크기의 정사각형을 탐색하면서 같은 숫자가 있는지 확인 
- 가장 큰 정사각형의 길이를 return
- 크기를 결정하는 것이므로 제곱해서 출력

 

💡CODE

const fs = require("fs");
const now = fs.readFileSync(0, "utf8").toString().trim().split("\n");

const NM = now.shift().split(" ");
const N = Number(NM[0]);
const M = Number(NM[1]);

function square() {
  let result = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      let limit = Math.min(N - i, M - j);
      for (let k = 0; k < limit; k++) {
        if (
          now[i][j] === now[i][j + k] &&
          now[i][j] === now[i + k][j] &&
          now[i][j] === now[i + k][j + k]
        ) {
          result = Math.max(result, k + 1);
        }
      }
    }
  }
  return result;
}
const Square = square();
console.log(Square ** 2);

 

💡시간복잡도

 

💡 틀린 이유 & 틀린 부분 수정

k를 1로 설정해서 첫번째 부분과 비교가 불가능했음

 

💡 다른 풀이 or 기억할정보

let start = now[i][j] 로 정의해서 간단한 식으로 풀었는데
이렇게 되면 배열이 아닌 수와 비교하게 되는거라 오류가 발생할 수 있음을 알게됨