[완전탐색][Java][BOJ] #1051. 숫자 정사각형

#완전탐색  #Silver3

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

🌷 문제 설명

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

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

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

 

입출력 예

입력	출력
3 5 42101 22100 22101	9
2 2 12 34	1
2 4 1255 3455	4
1 10 1234567890	1
11 10 9785409507 2055103694 0861396761 3073207669 1233049493 2300248968 9769239548 7984130001 1670020095 8894239889 4053971072	49

 

💡 해결 포인트

1.  인덱스값의 지표가 되어 줄 변수 k
- 뭔가 2중 포문을 돌리게 되면 그거 이상으로 포문 돌리고 싶지 않아 무서워지는데
- 나는 이제 느린 파이썬 대신 빠른 자바 돌리니까 두려워하지말자(?)

2. 범위
- 🤖 k 범위를 N 과 M 중 최솟값이 아니라, N-n, M-m 중 최솟값으로 설정하자 (범위가 지금보다 훨씬 작아져서 불필요한 연산 줄어듦!)

3. 불필요한 연산 제거
- 🤖 같은 값을 제곱해서 max를 매번 업데이트 하지 말고, 해당 값을 max 에 집어넣고, 최대 값인 max를 리턴할 때(출력할 때) 한 번만 제곱을 해주면 제곱연산을 한 번만 할 수 있음!

 

🌷 내 코드

1. 완전탐색

import java.util.*;
import java.io.*;

public class BOJ_1051 {
  public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] firstLine = br.readLine().split(" ");
    int N = Integer.parseInt(firstLine[0]); // 최대 50
    int M = Integer.parseInt(firstLine[1]);

    // 직사각형 받기
    int[][] map = new int[N][M];

    for (int i = 0; i < N; i++) {
      String[] line = br.readLine().split("");
      for (int j = 0; j < M; j++) {
        map[i][j] = Integer.parseInt(line[j]);
      }
    }

    // System.out.println(Arrays.deepToString(map));

    int max = 0;
    // 제일 왼쪽 포인트 (0.0)부터 시작해서 최대한 큰 정사각형인지 확인
    for (int n = 0; n < N; n++) {
      for (int m = 0; m < M; m++) {
        for (int k = 0; k < Math.min(N, M); k++) { // N, M 중 작은 값까지 확인(왜냐면 정사각형이니까)
          if (n + k < N && m + k < M) { 
            if (map[n][m] == map[n][m+k] && map[n][m] == map[n+k][m] && map[n][m] == map[n+k][m+k]) {
              if ( max < (k + 1) * (k + 1)) {
                max = (k + 1) * (k + 1);
              }
            }
          }
        } 
      }
    }

    System.out.println(max);

  }  
}

 

 

🌷 코멘트

이번 문제는 뭔가 푸는 것은 어렵지 않았고 이해도 나름 잘 돼서 지피티한테 어떻게 개선하면 좋을지 까지 물어봤따.
범위를 잘 축소하는 것이 중요하다고는 생각하긴 했는데, 그 이상으로 생각이 뻗질 못했던 것 같다. (고민 안하고 빨리 자고싶음 이슈)

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com