[프로그래머스] 가장 큰 정사각형 찾기

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스

코드

class Solution
{
    public int solution(int [][]board)
    {

		
		// 우측하단부터 만들려고하는데, 길이가 1인경우에도 검사 될 수 있도록 크기가1더 큰 배열을 새로 만든다.
		int[][] newBoard = new int[board.length+1][board[0].length+1];
		
		for ( int i = 0 ; i < board.length; i++ ) {
			for ( int j = 0 ; j < board[0].length; j++ ) {
				newBoard[i+1][j+1] = board[i][j];
			}
		}
		
		int max = 0;
		
		// 모든 board를 확인한다.
		for ( int i = 1 ; i < newBoard.length; i ++ ) {
			for ( int j = 1 ; j < newBoard[i].length; j++ ) {

				// 2x2 사각형의 우측하단을 기준으로 정사각형이 되는 경우에는 변의 길이를 기록해간다.

				// 우측하단이 기준인 이유는 마지막 좌표의 값을 구하기전에는 나머지 board들은 계산이 끝나야하기 때문이다.

				// 변의 길이는 2x2 정사각형을 구성하는 변들의 최솟값이다.
				if ( newBoard[i][j] >= 1 ) {
					
					//좌측
					int left = newBoard[i-1][j];
					//상단
					int up = newBoard[i][j-1];
					//좌측상단(대각선)
					int leftDiagonal = newBoard[i-1][j-1];

					int min = Math.min(left, up);
					min = Math.min(min, leftDiagonal);

					newBoard[i][j] = min+1;

					max = Math.max(max, min+1);
				}
			}
		}

		return (int)Math.pow(max, 2);
	
    }
}

제출 결과

후기

문제의 핵심은 2*2 크기의 정사각형을 찾아가면서 변의 길이를 기록해주는 것이다.

(0,0) 1	(0,1) 0	(0,2) 1
(1,0) 0	(1,1) 1	(1,2) 1
(2,0) 0	(2,1) 1	(2,2) 1

예를 들어 위와 같이 주어졌을 때, 2*2의 정사각형을 확인하는 방법은 

 

(1,1)부터 시작해서 1인 경우에만 [ 상단, 좌측, 좌측 상단 ]의 값을 확인한 후 최솟값+1을 해주면 되는데..

 

최솟값 +1을 하는 이유는 아래예시를 보면서 이해해 보자.

 

위의 예시에서 1,1부터 보게 되면 

 

(1,1) -> [ 상단 : 0, 좌측 : 0, 좌측 상단 : 1 ] 이므로 -> 1로 바꿔 줌

(1,2) -> [ 상단 : 1, 좌측 : 1, 좌측상단 : 0 ] 이므로 -> 1로 바꿔 줌

(2,1) -> [ 상단 : 1, 좌측 : 0, 좌측상단 : 0 ] 이므로 -> 1로 바꿔 줌

(2,2) -> [ 상단 : 1, 좌측 : 1, 좌측 상단 : 1 ] 이므로 -> 2로 바꿔 줌

 

즉, 0이하나라도 있는 경우는 2*2의 정사각형을 만들 수 없는 경우이다. 

왜?

조각이 비게되니깐.

 

그러나 모든 조각이 1이라면 가능하다!

 

똑같은 방식으로 아래 정사각형을 풀이해 보자.

 

1	1	1
1	1	1
1	1	1

(1,1) -> [ 상단 : 1 , 좌측 : 1 , 좌측 상단 : 1 ] 이므로 -> 2로 바꿔 줌

1	1	1
1	2	1
1	1	1

 

(1,2) -> [ 상단 : 1 ,좌측 : 1 ,좌측상단 : 1 ] 이므로 -> 2로 바꿔 줌

1	1	1
1	2	2
1	1	1

 

(2,1) -> [ 상단 : 1 ,좌측 : 1 ,좌측상단 : 1 ] 이므로 -> 2로 바꿔 줌

1	1	1
1	2	2
1	2	1

 

(2,2) -> [ 상단 : 2 ,좌측 : 2 ,좌측상단 : 2 ] 이므로 -> 3로 바꿔 줌

1	1	1
1	2	2
1	2	3

 

이런 규칙으로 2*2의 정사각형을 만들면서 최대 변의 크기를 우측 하단에 기록해주면 최대 크기의 정사각형을 구할 수 있게 된다.

 

( n크기의 정사각형을 만들 수 있는 경우 해당 좌표에 기록되고, 이게 누적되면서 최대 정사각형의 크기를 자연스럽게 구하고 있다... )

 

그런데 이렇게 1,1부터 보게 됐을 때는 아래와 같은 경우의 수를 캐치할 수 없다.

 

0

1

0

이렇게 주어졌을 때, 최대 크기의 정사각형은 1이다.

0

0

1

이렇게 주어졌을 때도 1이다.

 

이런 경우를 해결하기 위해서 처음에 배열의 크기를 전체 크기+1로 만들어서 int [0][n] 번째 값과 int [n][0] 번째 값을 빈 값으로 채워준다.

0	0	0	0
0	0	1	0

 

0	0
0	0
0	0
0	1

이렇게 만들면 길이가 1인 경우에도 1,1부터 이상 없이 볼 수 있게 되고, 채워진 값 0으로 인해 원래 1,1의 값은 변동이 생길 수 없다.

 

Q. 1*1의 정사각형이 나란히 놓여있을 때, 만들 수 있는 최대 크기는 몇인지 구할 수 있겠는가??