[99클럽 코테 스터디 12일차 TIL / 백준] 1051 - 숫자 정사각형 (브루트포스)

99클럽 코테스터디 12일차 TIL
KeyWord : 브루트포스

문제

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

입력

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

출력

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

 

---

 

풀이

간단한 브루트포스 문제로 코드 구현 능력만 있다면 쉽게 해결할 수 있는 문제이다.

왼쪽 위의 꼭짓점을 기준으로 하여 정사각형을 만들면서 완전탐색을 하면 된다.

42101
22100
22101

이 입력을 기준으로 (0, 0)의 4부터 (2,4)의 1까지를 전부 정사각형의 왼쪽 위 꼭짓점으로 가정하여 완전탐색을 진행하면 된다는 의미이다.

예를 들어, 첫 번째 완전탐색에서 만들어질 수 있는 정사각형은 아래와 같다.

4

4 2
2 2

4 2 1
2 2 1
2 2 2

여기서 문제의 해가 될 수 있는 정사각형은 1번이므로, 현재 상황에서 가장 큰 정사각형의 넓이는 1이 된다. 이를 기록해두고 다음 탐색을 진행한다.

주의할 점은 길이가 1인 정사각형도 만들어질 수 있다는 것과 구현 시 Array Index Out of Bounds Exception 에러가 나타나지 않게끔 배열의 인덱스만 잘 설정해주면 된다는 것 정도다.

이것만 고려하면 어렵지 않게 해결할 수 있을 것이다.

 

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer stk = new StringTokenizer(br.readLine());  

        int N = Integer.parseInt(stk.nextToken());  
        int M = Integer.parseInt(stk.nextToken());  

        int[][] map = new int[N+1][M+1];  
        for (int i = 1; i < N+1; i++) {  
            String line = br.readLine();  
            for (int j = 1; j < M+1; j++) {  
                map[i][j] = line.charAt(j-1) - '0';  
            }  
        }  

        int maxSideLen = getMaxSideLen(N, M, map);  
        System.out.println(maxSideLen*maxSideLen);  
    }  

    private static int getMaxSideLen(int N, int M, int[][] map) {  
        int maxIdx = Math.min(N, M);  
        int maxSideLen = 1;  

        for (int x = 1; x <= N; x++) {  
            for (int y = 1; y <= M; y++) {  

                int curNum = map[x][y];  
                for (int curSideLen = 1; curSideLen <= maxIdx; curSideLen++) {  
                    if(curSideLen < maxSideLen) continue;  

                    int nextX = x + curSideLen - 1;  
                    int nextY = y + curSideLen - 1;  

                    if(nextX > N || nextY > M) {  
                        continue;  
                    }  

                    if (map[nextX][nextY] == curNum && map[x][nextY] == curNum && map[nextX][y] == curNum) {  
                        maxSideLen = Math.max(maxSideLen, curSideLen);  
                    }  
                }  
            }  
        }  
        return maxSideLen;  
    }  
}