[백준] 1051번: 숫자 정사각형(완전 탐색, 구현)

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

1051번: 숫자 정사각형

틀린코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int M = scan.nextInt();
		int[][] arr = new int[N][M];
		int max = 0;
		int row = 0;
		int col = 0;
		boolean flag = true;
		
		// 2차원 배열에 값 넣기
		for(int i=0; i<N; i++) {
			String str = scan.next();
			for(int j=0; j<M; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		/*
		 * 1x1 , 2x2 , 3x3 , ... 가능한 모든 정사각형을 완전 탐색으로 찾는다.
		 */
		while(true) {
			int area = 0;
			if(!flag)
				break;
			
			for(int i=0; i<N-1; i++) {
				for(int j=0; j<M-1; j++) {
					
					// 비교할 수 있는 가로 또는 세로의 꼭짓점이 배열의 크기를 벗어난 경우
					if(row + i >=N || col + j >= M) {
						flag = false;
						break;
					}
					
					/*
					 * 네 개의 꼭짓점이 정사각형을 이루고 꼭짓점에 쓰여있는 수가 같을 때,
					 * A B 
					 * C D 
					 * 위 4개에서, A = B && A = C && A = D 이면 4개의 수가 같다고 판단.
					 */
					if(arr[i][j] == arr[i][j+col] && arr[i][j] == arr[i+row][j] && arr[i][j] == arr[i+row][j+col]) {
						// 한변의 길이 = 두 점의 좌표를 뺀 후 +1을함, (0,2) (0,4)의 길이 => 3
						int width = (Math.abs(j-i)) + 1;
						area = width * width;
					}
				}
			}
			
			max = Math.max(max, area);
			row ++;
			col ++;
		}
		System.out.println(max);
		scan.close();
	}

}

풀이

 

처음 문제에서 N, M의 범위가 50까지밖에 안되서 완전탐색으로 해도 충분히 시간초과가 날 것 같지 않아서 

정사각형이 1x1부터 시작해서 가장 큰 정사각형 nxn 까지 비교해가며 4개의 꼭짓점이 같은수를 찾고, 가장 큰 넓이를 구하도록 생각하고 코드를 작성했는데, 위 코드는 테스트케이스만 통과하고 틀렸다고 나온다.

도저히 떠오르지가 않아서 타 블로그들을 참고했다.

 

최종 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int M = scan.nextInt();
		int[][] arr = new int[N][M];
		final int MIN = Math.min(N, M);
		int area = 0;
		int maxArea = 0;
		
		// 2차원 배열에 값 넣기
		for(int i=0; i<N; i++) {
			String str = scan.next();
			for(int j=0; j<M; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				for(int k=0; k<MIN; k++) {
					if(i+k < N && j+k < M) {	// 배열 범위 이내
						
						// 4개의 꼭짓점이 정사각형이 되는 조건
						if(arr[i][j] == arr[i][j+k] && arr[i][j] == arr[i+k][j] && arr[i][j] == arr[i+k][j+k]) {
							area = (k+1) * (k+1);
							maxArea = Math.max(maxArea, area);
						}
					}
				}
			}
		}
		
		System.out.println(maxArea);
		scan.close();
	}

}

풀이

먼저 주어진 N, M 중 더 큰값을 찾는다.

문제에서 3 x 5로 주어진 경우, 최대로 가능한 정사각형은 3 x 3이므로, 더 작은 3까지만 반복하면 되기 때문이다.

area = 4개의 꼭짓점이 정사각형일때, 넓이를 구하는 변수고

maxArea = 위 area와 비교해서 더 큰값을 저장하고, 최종적으로 출력할 변수다.

i+k 와 j+k가 각각 M, N 보다 작아야 배열의 범위 이내라고 할 수 있다.

4개의 꼭짓점이 같을 조건은 3개의 꼭짓점만 확인해주면 된다.

(0,0) , (0,1)

(1,0) , (1,1)

위와 같이 4개의 점이 있을때, A = B && A = C && A = D 이면 자동적으로 B = C = D 가 보장되기 때문이다.

또한 4개의 점을 찾기 위해 인덱스를 조작해야하는데, 행과 열, 행열에 각각 k를 더하면 일정한 4개의 꼭짓점이 된다.

 

 

 

* 뭔가 시간복잡도에 대해 약간(?)은 감이 잡히는 것 같다.

위 문제의 경우도 O(n^3) 이지만, 각각의 범위는 50이므로 50^3 으로 충분한 시간인 것 같다.

보통 1초당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다고 한다.