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

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

---

언어 : Java

풀이 방법 : BFS or Dynamic Programing

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

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

 

간단한 문제 설명

N x M 이차원 배열에서 1로 채워진 정사각형 중 가장 큰 넓이의 정사각형을 찾아 넓이를 출력하는 문제 (N과 M은 1000이하)

 

풀이 과정

정확성 테스트

=> BFS방식으로 탐색했다.

1을 만나면 우, 하, 하우를 탐색해서 1이면 Queue에 넣어줬다. (아래 그림 참조)

1) 1을 만나면 우, 하, 하우를 탐색. 각각이 1이면 Queue에 넣기.

 2) Queue에 있는거 꺼내서 다시 우, 하, 하우를 탐색, Queue에 넣기 반복하면서 0을 만나거나 범위를 벗어나면 최대값 갱신.

 

효율성 테스트

=> BFS방식으로는 별별 가지치기를 해도.... 때려죽어도 안되더라.

DP로 풀었다. (아래 방식 참조)

1) D배열을 선언하고 맨 첫줄은 그대로 D에 넣어준다.

 

2) 두번째줄을 탐색한다. D배열에서 탐색하는 칸을 기준으로 왼, 위, 왼위를 검사해준다.
* 1열은 어차피 크기가 1인 정사각형밖에 만들 수 없기 때문에 0이면 0을 기록하고, 1이면 1을 기록한다.

 

3) 왼, 위, 왼위를 탐색했을 때 0이 아니라는 것은 해당 크기의 정사각형이 각 칸을 오른쪽 아래로 하여 존재한다는 뜻이다.

 

4) 왼, 위, 왼위의 조건에 맞게 가능한 최대 정사각형의 크기를 적어준다.

 

 

소스코드

 BFS코드 (정확도 테스트 O / 효율성 테스트 X)

import java.util.LinkedList; import java.util.Queue;
 
class Solution
{
   static class info {
        int r, c;
 
        public info(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    private static int[] dr = { 0, 1, 1 }; // 우, 하, 우하
    private static int[] dc = { 1, 0, 1 };
    public static int solution(int [][]board)
    {
        int ans = 0;
        
        int size_1 = board.length;
        int size_2 = board[0].length;
        
        for (int i = 0; i < size_1; i++) {
            if(size_1 - i <=  ans) break;
            
            for (int j = 0; j < size_2; j++) {
                if(size_2 - j <= ans) break;
                if(board[i][j] != 0) {
                    int tmp = search(i,j,size_1,size_2,board);
                    if(ans < tmp)
                        ans = tmp;
                }
                
            }
            
        }
        
        
        return ans*ans;
    }
    
    private static int search(int i, int j, int size1, int size2, int[][] board) {
        Queue<info> qu = new LinkedList<>();
        qu.add(new info(i, j));
        
        boolean[][] visited = new boolean[size1][size2];
        visited[i][j] = true;
        int size = 1;
 
        exit: while (true) {
            int quSize = qu.size();
            
            for (int k = 0; k < quSize; k++) {
                info dot = qu.poll();
                int r = dot.r;
                int c = dot.c;
 
                for (int t = 0; t < 3; t++) {
                    int nr = r + dr[t];
                    int nc = c + dc[t];
                    if (nr >= 0 && nc >= 0 && nr < size1 && nc < size2) {
                        if (board[nr][nc] != 1)
                            break exit;
                        if (!visited[nr][nc]) {
                            visited[nr][nc] = true;
                            qu.add(new info(nr, nc));
                        }
                    } else
                        break exit;
                }
            }
 
            size++;
        }
        return size;
 
    }
}

class Solution
{
      public static int solution(int [][]board)
    {
        int ans = 0;
        
        int sizeR = board.length;
        int sizeC = board[0].length;
        
        int[][] DP = new int[2][board[0].length];
        
        //첫째줄은 그냥 복사해주기 (대신 최대값은 갱신해준다.)
        for (int i = 0; i < sizeC; i++) {
            DP[0][i] = board[0][i];
            if(DP[0][i] > ans)
                ans = DP[0][i];
        }
        
                for (int i = 1; i < sizeR; i++) {
            for (int j = 0; j < sizeC; j++) {
                
                if(board[i][j] == 0)
                    DP[1][j] = 0;
                else {
                    if(j == 0)
                        DP[1][j] = 1;
                    else {
                        DP[1][j] = 1;
                        if(DP[1][j-1] == 0 | DP[0][j] == 0 | DP[0][j-1] == 0) //셋 중에 하나라도 0이면
                            DP[1][j] = 1;
                        else if(DP[1][j-1] == DP[0][j] && DP[0][j] == DP[0][j-1]) //셋 다 같으면
                            DP[1][j] = DP[0][j] + 1;
                        else { //셋 다 다르면
                            if(DP[1][j-1] <= DP[0][j-1] && DP[1][j-1] <= DP[0][j])
                                DP[1][j] = DP[1][j-1] + 1;
                            else if(DP[0][j-1] <= DP[1][j-1] && DP[0][j-1] <= DP[0][j])
                                DP[1][j] = DP[0][j-1] + 1;
                            else if(DP[0][j] <= DP[0][j-1] && DP[0][j] <= DP[1][j-1])
                                DP[1][j] = DP[0][j] + 1;
                        }
                    }
                }
                
                if(DP[1][j] > ans)
                    ans = DP[1][j];
            }
            
            for (int j = 0; j < sizeC; j++) {
                DP[0][j] = DP[1][j];
            }
            
        }
        
        return ans*ans;
    }
}