[백준 / 1051번 / JAVA / 구현]

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

1051번: 숫자 정사각형

시간을 줄이려면 스캐너보다 버퍼를 사용하자

 

#문제 설명

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

 

#접근 방법

직사각형 속 꼭짓점 4군데의 수가 같은 최대 크기의 정사각형을 찾아야한다.

최대 크기의 정사각형은 행과 열중 더 작은 수를 기준으로 만들어야한다, 큰 수로는 정사각형을 만들 수  없기 때문

2차원 배열 rectangle에 수를 다 입력하여 직사각형을 만들고 0, 0 꼭짓점을 기준으로 행, 열 중 작은 수를 넣은 변수 search의 크기만큼 나머지 꼭짓점 3군데의 숫자를 비교하고 다 같을 시 search를 제곱한 후 출력하고 종료한다.

 

★처음엔 break를 사용해서 반복문을 빠져나가려했으나 break는 해당 반복문이나 조건문만 빠져나가서 실행 순서가 꼬였는데 찾아보니 return을 사용할 경우 전체 반복문을 빠져나갈 수 있다고한다.

import java.io.*;

public class Main{

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

        int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int [][]rectangle = new int[N][M];
		
		for(int i=0; i<N; i++) {
			String row = br.readLine();
			
			for(int j=0; j<M; j++) {
				
				rectangle[i][j] = row.charAt(j) - 48; // 아스키코드 형태라 -48해줘서 정수를 맞춰준다.
			}
		}
		
		int search = Math.min(N, M);
		
		while(true) {
			
			for(int i=0; i<= N-search; i++) {
				for(int j=0; j<= M-search; j++) {
					int n = rectangle[i][j]; // 기준 꼭짓점
					
					if(n == rectangle[i][j+(search-1)] 
					&& n == rectangle[i+(search-1)][j] 
					&& n == rectangle[i+(search-1)][j+(search-1)]) {
						System.out.println(search*search);
						return; // break는 가장 가까운 반복문만 탈출하나 return은 메소드 자체를 탈출
					}
				}
				
			}
			search--;
		}
	}

}