[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)1051번, 숫자 정사각형

문제 링크

1051번: 숫자 정사각형

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 꼭짓점에 쓰여있는 수가 모두 같은 가장 큰 정사각형의 넓이를 결과로 출력합니다.

2. 정사각형은 행과 열이 평행해야 합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 정사각형이 될 수 있는 큰 경우부터 탐색합니다.

 

3. 가장 먼저 찾은 정사각형의 넓이를 결과로 출력합니다.

 

 

정사각형 확인하기

 

문제에서는 가장 큰 넓이의 정사각형을 구해야합니다.

 

정사각형이 될 수 있는 경우 중 가장 큰 값부터 탐색을 진행합니다.

 

정사각형이 될 수 있는 최대의 경우

 

N과 M 중 작은 값이 정사각형이 될 수 있는 최대의 경우입니다.

 

탐색할 수 있는 기준 꼭짓점은

 

[0][0] ~ [N-크기][M-크기]

 

예를 들어 N = 3, M = 3일 때

 

정사각형의 크기가 2일 때 기준 꼭짓점이 가능한 곳은

 

[0][0] ~ [1][1]

 

가능	가능
가능	가능

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 3

 

M = 5

 

4	2	1	0	1
2	2	1	0	0
2	2	1	0	1

 

2. 정사각형이 될 수 있는 큰 경우부터 탐색합니다.

 

정사각형이 될 수 있는 최대 경우

 

3(N) < 5(M)

 

최대의 경우 : 3

 

정사각형의 길이가 3일 때 탐색

 

탐색할 수 있는 기준 꼭짓점

 

[0][0] ~ [0][2]

 

가능	가능	가능

 

[0][0] 탐색

 

4	2	1	0	1
2	2	1	0	0
2	2	1	0	1

꼭짓점에 값들이 다르기 때문에 조건에 맞는 정사각형 X

 

[0][1] 탐색

 

4	2	1	0	1
2	2	1	0	0
2	2	1	0	1

꼭짓점에 값들이 다르기 때문에 조건에 맞는 정사각형 X

 

[0][2] 탐색

 

4	2	1	0	1
2	2	1	0	0
2	2	1	0	1

꼭짓점에 값들이 다르기 때문에 조건에 맞는 정사각형 O

 

 

3. 가장 먼저 찾은 정사각형의 넓이를 결과로 출력합니다.

 

가장 먼저 찾은 정사각형의 크기 : 3

넓이 : 3 × 3 = 9

 

정사각형의 넓이 9를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용해서 N과 M을 띄어쓰기 기준 나누었습니다.
• Math.min을 이용해서 정사각형의 가장 큰 경우를 구하였습니다.
• 기준 꼭짓점으로 탐색하여 조건에 만족하는 정사각형이 찾습니다.
• 가장 먼저 발견된 정사각형의 넓이를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 기준 꼭짓점 기준 조건에 만족하는 정사각형인지 확인하는 함수입니다.

 

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

public class Main{
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int size = Math.min(N,M);	//정사각형 최대의 경우 구하기
        boolean check = false;
        arr = new int[N][M];
        //입력되는 직사각형 값 저장
        for(int i=0;i<N;i++){
            String info = br.readLine();
            for(int j=0;j<M;j++)
                arr[i][j] = Character.getNumericValue(info.charAt(j));
        }
        //정사각형 큰 경우부터 탐색 시작
        while(size != 1){
            //기준 꼭짓점들에서 탐색
            for(int i=0;i<=N-size;i++){
                for(int j=0;j<=M-size;j++)
                    if(search(i, j, size-1)){
                        check = true;	//조건 만족하는 정사각형 찾았을 때
                        break;
                    }
                if(check)	//정사각형 찾았으므로 탐색 종료
                    break;
            }
            if(check)	//정사각형 찾았으므로 탐색 종료
                break;
            size--;	//정사각형 크기 줄이기
        }
        int answer = size * size;	//넓이 구하기
        bw.write(answer + "");	//넓이 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //정사각형 꼭짓점이 모두 같은값인지 확인하는 함수
    static boolean search(int y, int x, int size){
        if(arr[y][x] == arr[y + size][x] && arr[y][x] == arr[y][x+size] &&
                arr[y][x] == arr[y+size][x+size])
            return true;
        return false;
    }
}