[DP] 가장 큰 정사각형 찾기 (find Largest Square)

Programmers Level_03

가장 큰 정사각형 찾기 (find Largest Square)

O와 X로 채워진 표가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 O로 이루어진 가장 큰 정사각형을 찾아 넓이를 반환하는 findLargestSquare 함수를 완성하세요. 예를 들어

1	2	3	4	5
X	O	O	O	X
X	O	O	O	O
X	X	O	O	O
X	X	O	O	O
X	X	X	X	X

가 있다면 정답은

1	2	3	4	5
X	O	O	O	X
X	O	O	O	O
X	X	O	O	O
X	X	O	O	O
X	X	X	X	X

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

저는 점화식 DP로 풀었습니다.

1 1

1 1 

인 경우 (1,1) 에 있는 값은 (1,0),(0,0),(0,1) 3방향에 있는 값들이 모두 1이상이면 이 3가지 값 중에 가장 작은 값에서 +1을 한 값이 결국 (1,1)의 값이 됩니다. 즉 아래와 같이 됩니다.

1 1

1 2

이 말은 크기가 2인 정사각형이지요.. 넓이는 2*2 = 4입니다.

이런식의 원리로 하다 보면... 아래와 같은 경우는 다음과 같이 변환되겠네요...

1 1 1

1 1 1

1 1 1

-------------------

1 1 1

1 2 2

1 2 3

그럼 3*3 = 9 로 가장 큰 정사각형은 9라는 사실을 알 수 있습니다. 

또 한 가지 팁을 드리면, 열과 행을 +1씩 더 크게 잡아서 0열, 0행에 속해있는 값들도 예외없이 비교할 수 있도록 한다는 점을 알아두셔야 합니다. 아래 코드를 곱씹어 보시면 이해가 되실 겁니다...

package Programmers.level04;

public class findLargestSquare2 {

	 public static void main(String[] args)
	    {
		 findLargestSquare2 test = new findLargestSquare2();
					char [][]board ={
					{'X','O','O','O','X'},
					{'X','O','O','O','O'},
					{'X','X','O','O','O'},
					{'X','X','O','O','O'},
					{'X','X','X','X','X'}};

	        System.out.println(test.findLargestSquare(board));
	    }

	 public int findLargestSquare(char [][]board)
	    {
	        int answer = 0;
	        int [][]dp = 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++){
	        		if(board[i][j]=='O'){
	        			dp[i+1][j+1] = 1;
	        		}
	        	}
	        }
	        
	        for(int i=0; i<dp.length; i++){
	        	for(int j=0; j<dp[0].length; j++){
	        		if(dp[i][j]>=1 && dp[i][j-1]>=1 && dp[i-1][j-1]>=1 && dp[i-1][j]>=1){
	        			dp[i][j] = Math.min(dp[i][j-1],Math.min(dp[i-1][j-1], dp[i-1][j]))+1; 
	        		}
	        	}
	        }

	        //printArray(dp);
	        for(int i=0; i<dp.length; i++){
	        	for(int j=0; j<dp[0].length; j++){
	        		answer = Math.max(dp[i][j], answer);
	        	}
	        }
	        
	        return answer*answer;
	    }
	 
	 private static void printArray(int[][] ground) {
			for(int i=0; i<ground.length; i++){
				for(int j=0; j<ground[0].length; j++){
					System.out.print(ground[i][j]+" ");
				}
				System.out.println();
			}
		}
}