Solution.java (Brute Force)

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                for (int k = 0; k < Math.min(board[0].length - j, board.length - i); k++) {
                    boolean chk = true;
                    for (int l = 0; l <= k; l++) {
                        if (board[i + l][j + k] == 0 || board[i + k][j + l] == 0) {
                            chk = false;
                            break;
                        }
                    }
                    
                    if (!chk) break;
                    
                    if (answer < (k + 1) * (k + 1)) answer = (k + 1) * (k + 1);
                }
            }
        }

        return answer;
    }
}

완전탐색으로 풀어보았는데 역시나 시간초과가 났다.

질문하기를 참고해보니 DP 문제인것같다. 다시 풀어봐야겠다.

---

Solution.java (DP)

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        
        for (int i = 0; i < board[0].length; i++) {
            if (board[0][i] == 1) {
                answer = 1;
                break;
            }
        }
        
        if (answer == 0) {
            for (int i = 0; i < board.length; i++) {
                if (board[i][0] == 1) {
                    answer = 1;
                    break;
                }
            }
        }

        for (int i = 1; i < board.length; i++) {
            for (int j = 1; j < board[0].length; j++) {
                if (board[i][j] == 1) {
                    board[i][j] = Math.min(Math.min(board[i - 1][j - 1], board[i - 1][j]), board[i][j - 1]) + 1;
                    if (answer < board[i][j]) answer = board[i][j];
                }
            }
        }
        
        answer *= answer;

        return answer;
    }
}

바로 해결되었다. 역시 DP는 생각하기가 어려운것같다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges