프로그래머스 12905번
https://school.programmers.co.kr/learn/courses/30/lessons/12905

문제

---

생각하기

---

• 처음에 그냥 DFS로 푸는 문제인 줄 알았는데,

• 규칙이 있어서 DP로 풀어야하는 문제였음

동작

탑 다운과 바텀 업 2가지로 풀이했는데, 탑 다운이 아무래도 시간은 더 오래 걸릴 수 밖에없다.

⭐ 바텀 업에서 하나 깨달은 것은 memo배열을 활용하기 위해서는 누적된 값을 활용해야 하기 때문에 2차원 배열의 순환 방향과

방향 탐색에서는 반대방향으로 가야한다는 것이다.

즉, 배열 순환이 0 -> n 순으로 간다면, 내가 정사각형이 되는 구간인지 탐색을 하기 위해서는 n -> 0 방향으로 가야한다.

이렇게 하면 0에서 시작된 1값이 다음 순환에서 1의 값을 끌어올림으로써 memo의 누적값을 활용할 수 있게된다.

결과

코드

---

TopDown

import java.util.*;

class Solution {
    public static int[][] memo;
    
    public int solution(int [][]board) {
        int ans = 0;
        int n = board.length;
        int m = board[0].length;
        input(n, m, board);
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(board[i][j] == 1) {
                    ans = Math.max(ans, topDown(board, i, j));
                }
            }
        }

        return ans * ans;
    } // End of solution()
    
    public int topDown(int[][] board, int x, int y) {
        if(x < 0 || y < 0 || board[x][y] == 0) return 0;
        if(memo[x][y] != -1) return memo[x][y];
        
        memo[x][y] = Math.min( Math.min(topDown(board, x - 1, y), topDown(board, x, y - 1)), topDown(board, x - 1, y - 1)) + 1;
        
        return memo[x][y];
    } // End of topDown()
    
    public void input(int n, int m, int[][] board) {
        memo = new int[n][m];
        for(int i=0; i<n; i++) {
            Arrays.fill(memo[i], -1);
        }
    } // End of input()
} // End of Solution class

BottomUp

import java.util.*;

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

        int n = board.length;
        int m = board[0].length;
        int[][] memo = new int[n + 1][m + 1];
        
        // 누적되는 사이즈 크기를 계산하기 위해 memoization을 활용하려면
        // 2차원 배열 순환 방향과, 탐색방향이 반대가 되어야 한다.
        for(int i=n-1; i>=0; i--) {
            for(int j=m-1; j>=0; j--) {
                if(board[i][j] == 1) {
                    memo[i][j] = Math.min(Math.min(memo[i+1][j], memo[i][j+1]), memo[i+1][j+1]) + 1;
                    ans = Math.max(ans, memo[i][j]);
                }
            }
        }

        return ans * ans;
    } // End of solution()
} // End of Solution class