가장 큰 정사각형 찾기

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를 반환해 주면 됩니다.

처음에는 "모든 칸에서 각 길이만큼 가능한 정사각형을 구해서 최대값을 저장한다."라는 생각으로 n중 for문을 사용했는데 보기좋게 타임아웃이 났다. 그래서 좀 더 생각해보니 d[n,m]이 (n,m)의 최대 정사각형 크기라면 d[i-1,j-1], d[i, j-1], d[i-1, j]의 최소값 + 1이 d[i,j]값이 된다는 사실을 알아냈다. 어떤 정사각형이 만들어지려면 그것보다 한칸 앞의 칸에서도 정사각형이 만들어져야하기 때문이다. 스스로도 생각하고 놀랐다. 뭔가 성장한 느낌이 또 들었다. ㅎㅎ

먼저 첫 행, 첫 열을 검사하여 초기화 해주고 (1,1)부터 반복문을 돌려주었다.

그런데 문제는 제출을 하니 정답이 아니라고 나온다. 검색해서 다른 답과 비교해도 다를 것이 없는데... 사이트 내의 에러인 듯 하다.

//n중 for문(timeout)
class LargestSquare {
    public int findLargestSquare(char[][] board) {
        int answer = 0;
        int size = 0;
        boolean token = true;
 
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int edge = Integer.min(i, j);
                for (int m = 0; m <= edge; m++) {
                    for (int k = i; k > i-edge; k--) {
                        for (int l = j; l > j-edge; l--) {
                            if (board[k][l] == 'X') {
                                token = false;
                            }
 
                        }
                    }
                    if(token==true) {
                        size=edge;
                    } else {
                        token=true;
                        break;
                    }
                }
                answer = Integer.max(answer, size);
            }
        }
 
        return answer*answer;
    }
 
    public static void main(String[] args) {
        LargestSquare test = new LargestSquare();
        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));
    }
}
 
//dp
class LargestSquare {
    public int findLargestSquare(char[][] board) {
        int answer = 0;
        int[][] arr = new int[board.length][board[0].length];
 
        for(int i = 0; i<board.length;i++) {
            arr[0][i] = board[0][i] == 'O' ? 1 : 0;
        }
        for(int j = 0; j<board[0].length;j++) {
            arr[j][0] = board[j][0] == 'O' ? 1 : 0;
        }
        
        for(int i = 1;i<arr.length;i++) {
            for(int j = 1;j<arr[0].length;j++) {
                if(board[i][j] == 'O') {
                    arr[i][j] = Integer.min(Integer.min(arr[i-1][j-1], arr[i][j-1]), arr[i-1][j])+1;
                    answer= answer > arr[i][j] ? answer : arr[i][j];
                } else {
                    arr[i][j] = 0;
                }
            }
        }
 
        return answer*answer;
    }
 
    public static void main(String[] args) {
        LargestSquare test = new LargestSquare();
        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));
    }
}