백준 1051: 숫자 정사각형 - javacript(구현)

문제 출처 

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

1051번: 숫자 정사각형

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

예제 입력 1 복사

3 5
42101
22100
22101

예제 출력 1 복사

9

예제 입력 2 복사

2 2
12
34

예제 출력 2 복사

1

예제 입력 3 복사

2 4
1255
3455

예제 출력 3 복사

4

예제 입력 4 복사

1 10
1234567890

예제 출력 4 복사

1

예제 입력 5 복사

11 10
9785409507
2055103694
0861396761
3073207669
1233049493
2300248968
9769239548
7984130001
1670020095
8894239889
4053971072

예제 출력 5 복사

49

 

문제 풀이 힌트 

세로가 3, 가로가 5인 직사각형에서 4개의 꼭짓점 수가 같은 정사각형을 찾는 문제였다. 

이 경우에 가장 큰 정사각형은 한 변의 길이가 3일 것이다. 

가장 큰 정사각형을 찾는 것이니, 나는 한변의 길이가 3이었을 때 사각형에서 꼭짓점이 다 같은 것을 찾아보고, 

없다면,,,, 한변의 길이가 2일 때, 

없다면,,, 한변의 길이가 1일 때,, ! 이런식으로 줄여나갈 것이다. 

 

그렇다면 이동은? 

나는 세로로 먼저 이동후, (for 반복문에서 'i') 가로로 이동할 것이다. (for 반복문에서 'j')

=> 이 이동방식이면 한변의 길이가 3이였을 때 정사각형 모양으로 전체 직사각형을 다 훑는 모양새가 된다. 

 

각 꼭짓점은 ? 

=> 1번 꼭짓점 (정사각형 왼쪽 위) `graph[i][j]`

2번 꼭짓점 (정사각형 왼쪽 아래) `graph[i+square-1][j]` 

3번 꼭짓점 (정사각형 오른쪽 위) `graph[i][j+square-1]`

4번 꼭짓점 (정사각형 오른쪽 아래) `graph[i+square-1][j+square-1]`

 

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N,M] = input.shift().split(' ').map(v => +v); 
const graph = Array.from({length: N}).map(()=> []); 
for(let i=0; i<input.length; i++){
   graph[i] = input[i].split('').map(v=> +v)
}

// 세로 아래로 이동 후, 가로 오른쪽으로 이동하면서 각 꼭짓점의 숫자가 일치하는지 센다. 
//만약 일치하지 않다면 숫자를 줄인 사각형을 찾는다. 

let square = Math.min(N,M); //N과 M 중 작은 숫자가 최대로 큰 경우의 정사각형이다  
while(square > 1){//한변의 길이가 2일 때까지만 찾아보기.
   for(let i=0; i<=N-square; i++){//세로 이동
    for(let j=0; j <= M-square; j++){ //가로 이동 
        if(graph[i][j] === graph[i+square-1][j+square-1] && graph[i+square-1][j] === graph[i][j+square-1] && graph[i][j] === graph[i+square-1][j]){
            console.log(square * square); //정사각형 넓이 
            return; //반복문 끝날 수 있도록 return 
        }
    }
}
square--;
}
console.log(1) // 한 변의 길이가 1인 정사각형일 때,

 

Only 문제 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N,M] = input.shift().split(' ').map(v => +v); 
const graph = Array.from({length: N}).map(()=> []); 
for(let i=0; i<input.length; i++){
   graph[i] = input[i].split('').map(v=> +v)
}

let square = Math.min(N,M); 
while(square >1){
   for(let i=0; i<=N-square; i++){//세로 이동
    for(let j=0; j <= M-square; j++){ //가로 이동 
        if(graph[i][j] === graph[i+square-1][j+square-1] && graph[i+square-1][j] === graph[i][j+square-1] && graph[i][j] === graph[i+square-1][j]){
            console.log(square * square); 
            return;
        }
    }
}
square--;
}
console.log(1)