[백준] 1051번 : 숫자 정사각형 (java)

1051번: 숫자 정사각형 (acmicpc.net)

1051번: 숫자 정사각형

어떻게 생각하고 문제를 풀었는가?

배열에 정사각형 구간을 설정하고, 각 꼭짓점의 문자가 모두 같은지 확인하여야 합니다.

좌상단 좌표를 for문 2개로 x와 y좌표를 선택, 문자가 같은 우상단 좌표를 얻었다면 좌하단, 우하단 좌표의 문자 비교를 통해 조건을 만족하는 정사각형 구간을 찾아내고 넓이를 구할 수 있습니다.

코드

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

class Main {
    static int N, M;
    static final int MIN_SIZE = 1;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(tokenizer.nextToken());
        M = Integer.parseInt(tokenizer.nextToken());
        String[] rectangularArr = new String[N];
        for(int i=0; i<N; i++){
            rectangularArr[i] = reader.readLine();
        }
        int size = MIN_SIZE;
        for(int top=0; top<N-1; top++){
            for(int left=0; left<M; left++){
                char value =rectangularArr[top].charAt(left);
                for(int right=M-1; right>left; right--){
                    if(value != rectangularArr[top].charAt(right)) continue;
                    int down = top + right - left;
                    if(down<N && isSameValue(rectangularArr[down].charAt(left), rectangularArr[down].charAt(right), value)){
                        size = Math.max(size, (down-top+1)*(right-left+1));
                        break;
                    }
                }
            }
        }
        System.out.println(size);
        reader.close();
    }
    static boolean isSameValue(char leftDown, char rightDown, char value){
        return leftDown == value && rightDown == value;
    }
}

3개의 for문을 사용하여 코드를 작성하였습니다.

정사각형의 좌상단 좌표를 설정하고, 같은 문자를 갖는 우측 좌표를 M-1부터 left+1까지 찾아 우상단 좌표를 설정합니다.

너비와 높이가 같도록 top + right - left로 down의 좌표를 구해 좌하단, 우하단 좌표의 문자와 비교하여 정사각형을 찾아냅니다.

우측 좌표를 찾는 반복문은 더 큰 너비를 갖는 정사각형의 발견이 이루어지면 다음 순회는 넓이 최대값을 찾는데 의미가 없으므로 break를 사용하여 속도를 향상시킬 수 있습니다.