mingssssss

1. 문제

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

2. 코드

import java.util. *;

class Solution {
    
    static int N;
    static int M;
    static int min;
    static int answer;
    static boolean flag;
    
    public int solution(int[][] board) {
        
        N = board.length;
        M = board[0].length;
                
        if (M == 1) {
            
            for (int i = 0; i < N; i++) {
                if (board[i][0] == 1) {
                    return 1;
                }
            }
            return 0;
            
        } else if (N == 1) {
            
            for (int j = 0; j < M; j++) {
                
                if (board[0][j] == 1) {
                    return 1;
                }
            }
            
            return 0;
        }
        
        int answer = 1;
        
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                                
                if (board[i][j] == 1) {
                                       
                    min = Math.min(Math.min(board[i - 1][j - 1], board[i - 1][j]), board[i][j - 1]);
                    board[i][j] = min + 1;
                   
                    answer = Math.max(board[i][j], answer);
                    flag = true;
                    
                }
            }
        }

        if (flag == false) {
            return 0;
        }
        
        return answer * answer;
    }
}

3. 리뷰

전형적인 bfs 탐색 문제인.. 줄 알았으나 O(N^4)으로 시간 초과과 나는 것을 간과했다.

이 문제는 DP를 이용한 탐색문제이다.

풀이법을 찾지 못 해서 구글링을 통해 해법을 찾았다.

https://zzang9ha.tistory.com/189

정사각형을 찾는 문제이므로, (1, 1)부터 시작해서 좌상, 상, 좌의 값의 최솟값을 찾아서

현재 탐색하는 위치에 1을 더해 저장해줬다.

탐색한 모든 곳이 1이라면, 현재 좌표는 2가 된다.

이런식으로 진행하다보면 배열의 최댓값은 정사각형의 한 변의 길이의 최댓값이 된다.

그 최댓값의 제곱값을 리턴해주면 된다.

하지만 행이 1이거나, 행이 0인 경우가 문제가 된다.

(1, 1)부터 탐색하기로 했으나 이 경우에는 해당 좌표가 존재하지 않는다.

따라서 각각의 경우를 조건문으로 만들어주고, for문을 돌려서 1이 나오면 1을 return하고,

for문을 다 돌아서 나온 경우는 1이 없다는 뜻이므로 0을 return했다.

또 다른 문제점은 배열의 모든 값이 0으로 채워져 있는 경우이다.

이 경우 0 * 0을 return하게 되는데, 이 값은 (-999999)^2 이다.
(https://programmers.co.kr/questions/12304)

따라서 boolean 변수를 하나 만들어서, 한 번이라도 1을 체크한 적이 있으면

0을 return 했다.

조금 지저분하게 짰지만, 최대한 이해할 수 있도록 가독성 측면을 고려해서 풀었다.