[알고리즘] 프로그래머스 가장 큰 정사각형 찾기 -BFS, DP- 자바

 

 

https://programmers.co.kr/learn/courses/30/lessons/12905?language=java 

코딩테스트 연습 - 가장 큰 정사각형 찾기

 

프로그래머스 가장 큰 정사각형 찾기 라는 문제를 풀었습니다. 

처음에 BFS문제로 접근했으나 밑에처럼 효율성에서 통과를 하지못했습니다.

 

 

효율성 ㅠㅠ

 

 

그래서 DP로 풀어야한다고하는데 

https://zzang9ha.tistory.com/189

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

이분꼐서 설명을 잘 해놓으셨으니 참고하시면 될 것 같습니다. !!

따라서 풀려고 했으나 오늘 일이 있어 다음에하는걸로!!ㅎㅎ

 

 

 

전 BFS로 풀었고 풀이는 다음과 같습니다.

 

[Java]

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    private static int[] dr = {0,1,1}; // 아래, 오른쪽밑대각선, 오른쪽
    private static int[] dc = {1, 0, 1};
    private static boolean[][] isVisited;
    private static int answer = 0;

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[][]{{0, 0, 1, 1}, {1, 1, 1, 1}});
    }

    private static void bfs(int r, int c, int[][] board) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(r, c, 1));
        isVisited[r][c] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 3; i++) {
                int r2 = point.r + dr[i];
                int c2 = point.c + dc[i];
                if (r2 >= 0 && r2 < board.length && c2 >= 0 && c2 < board[0].length) {
                    if(!isVisited[r2][c2]) {
                        if (board[r2][c2] == 0) {
                            answer = Math.max(answer, point.cnt);
                            return;
                        }
                        isVisited[r2][c2] = true;
                        queue.offer(new Point(r2, c2, point.cnt + 1));
                    }
                }else { //벽만남
                    answer = Math.max(answer, point.cnt);
                    return;
                }
            }
            if (queue.isEmpty()) { // 마지막값예외처리 (케이스 2번같이 길에막혀 탐색다한 경우)
                answer = Math.max(answer, point.cnt - 1);
            }
        }
    }

    public int solution(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                isVisited = new boolean[board.length][board[0].length];
                if (board[i][j] == 1) {
                    answer = Math.max(answer, 1);
                    bfs(i, j, board);
                }
            }
        }
        System.out.println(answer * answer);
        return answer * answer;
    }

    static class Point {
        int r;
        int c;
        int cnt;

        Point(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!