프로그래머스 가장 큰 정사각형 구하기 (실패 분석 - 시간초과)

접근

https://school.programmers.co.kr/learn/courses/30/lessons/12905

이 문제는 2차원 배열에서 가장 큰 정사각형을 구하는 문제입니다.
처음에 BFS를 이용하여 풀려고 시도했는데
생각해보니 Queue가 Overflow가 발생할거 같았습니다.
상태 배열을 사용할 수 없기 때문입니다.

정사각형이 겹치기도 하기 때문에 이미 지나간 부분에 대해서 다시 검사할 수 없다면
가장 큰 정사각형을 구하지 못할 수도 있습니다.
결국 모든 정사각형을 다 돌아야 하기 때문에 시간 초과가 발생했습니다.

BFS가 아닌 2차원 배열을 지나가면서 끝낼 수 있는 방법을 고안해야 합니다.
결국 다른 분의 풀이를 보고 힌트를 얻었습니다.

그림으로 표현해 보았습니다.
2중 for문만으로 가능한 방법입니다.

자신의 현 위치가 1이라면
(현 위치 기준 왼쪽, 위, 대각선의 세 위치)의 가장 작은 값 +1 = 현 위치 값
으로 갱신합니다.

저 방법은 현 위치가 1이라도 주변에 0이 존재하는 경우 1로 갱신됩니다.

풀이

import java.util.*;

class Solution{
    
     
    public int solution(int [][]board)
    {
        int answer = 1;
        int row = board.length;
        int col = board[0].length;

        if(checkZero(board)) return 0;
       
        
        for(int i=1;i<row ;i++){
            for(int j=1;j<col;j++){
                if(board[i][j]==0) continue;
                board[i][j]= Math.min(Math.min(board[i-1][j],board[i][j-1]),board[i-1][j-1])+1;
                answer = Math.max(answer,board[i][j]);
            }
        }
        
        return answer*answer;
    }
    
    static boolean checkZero(int[][] board){
        
        for(int[] subBoard : board){
            for(int s : subBoard){
                if(s==1) return false;
            }
        }
        return true;    
    }
    
}

풀이(시간초과 - bfs)

import java.util.*;

class Solution{
    
    static int[] x = {0,1,1};
    static int[] y = {1,0,1};
    static int level;
    
    static class XY{
        int x;
        int y;
        public XY(int x, int y){
            this.x = x;
            this.y = y;
        }
        
    }
    
    public int solution(int [][]board)
    {
        int answer = 0;

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        
        int row = board.length;
        int col = board[0].length;
        int max = Integer.MIN_VALUE;
        
        
        for(int i=0;i<row ;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]==1){
                    bfs(i,j,board);  
                    if(max<level) max=level;
                }
                
                
            }
        }
        
        return max*max;
    }
    
    static void bfs (int row, int col, int[][] board){
        level=0;
        Queue<XY> q = new LinkedList<>();
        q.offer(new XY(row,col));
        
        while(!q.isEmpty()){
            level++;
            int size = q.size();
            for(int i=0;i<size;i++){
                XY c = q.poll();
                boolean tag =false;
                
                for(int j=0;j<3;j++){
                    int newR = c.x + x[j];
                    int newC = c.y + y[j];
                    if(newR>board.length-1 || newC>board[0].length-1) {
                        tag =true;
                        q.clear();
                        break;
                    }else if(board[newR][newC]!=1){
                        tag=true;
                        q.clear();
                        break;
                    }else if(board[newR][newC]==1){
                        q.add(new XY(newR,newC));
                    }   
                }
                if(tag==true) break;
            }       
        }
        
    }
}