백준1051 - 숫자 정사각형 (완전탐색) node.js

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

문제는 다음과 같이, 꼭짓점에 쓰여있는 수가 모두 같은 가장 큰 정사각형을 찾는 문제다.

 

문제 풀이 방식

사각형의 크기를 의미하는 첫 줄에 주어진 데이터 N,M이 모두 50으로 작은 편이기에, 가능한 모든 상황을 탐색하는 완전탐색으로 접근했다. 각 좌표마다 가능한 크기만큼의 꼭짓점의 수를 구하고, 만약 모두 일치한다면 결괏값을 수정해주는 방식으로 로직을 구현했다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const [Y, X] = data.shift().split(" ").map(Number);
  const arr = data.map((el) => el.split("").map(Number));
  let result = 0;

  for (let i = 0; i < Y; i++) {
    for (let j = 0; j < X; j++) {
      const limit = Math.min(Y - i, X - j);
      for (let k = 1; k < limit; k++) {
        const verify = [arr[i][j + k], arr[i + k][j], arr[i + k][j + k]].every(
          (el) => el == arr[i][j]
        );
        if (verify && k > result) {
          result = k;
        }
      }
    }
  }
  console.log((result + 1) ** 2);
}

solution(input);