정사각형 검색하기..

gistfile1.txt

import java.util.ArrayList;
import java.util.List;

public class TryHelloWorld
{

    static class Point{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    // List<Point> initTruePoints = new ArrayList<>();

    /**
     * char 보드를 boolean 보드로 변환
     * @param board
     * @return
     */
    private boolean [][]toBoolBoard(char [][]board) {
        boolean[][] boolBoard = new boolean[board[0].length][board.length];
        for (int i = 0; i < board[0].length; i++)
            for (int j = 0; j < board.length; j++)
                boolBoard[i][j] = (board[i][j] == 'O');
        return boolBoard;
    }

    /**
     *  0 의 위치를 기억
     * @param board
     */
    private void initBoards(boolean [][]board){
        for (int i = 0; i < board[0].length; i++)
            for (int j = 0; j < board.length; j++)
                if(board[i][j]) initTruePoints.add(new Point(i,j));
    }

    public int findLargestSquare(char [][]board) {
        if(board.length==0) return 0;
        final boolean[][] boolBoard = toBoolBoard(board);
        // initBoards(boolBoard);

        int minialSize = (board[0].length > board.length) ? board.length : board[0].length;
        int initExpectedSize = minialSize / 2;

        if(foundAnySquare(boolBoard, initExpectedSize)){
            System.out.println("초기의 "+initExpectedSize+"사각형이 발견되어 증가하면서 검색.. ");
            initExpectedSize++;
            for(int i=initExpectedSize;i<=minialSize;i++)
                if(!foundAnySquare(boolBoard, i)){
                    System.out.println(i+"사각형이 발견되지 않았습니다. ");
                    return (int) Math.pow( i-1 , 2);
                }
        }else{
            System.out.println("초기의 "+initExpectedSize+"사각형에서 발견되지 않아 감소하면서 검색.. ");
            for(int i=initExpectedSize;i>0;i--)
                if(foundAnySquare(boolBoard, i)) return (int) Math.pow(i,2);
        }
        return 0;
    }

    private boolean foundAnySquare(boolean[][] board, int expectSize){
        System.out.println(expectSize+"사각형을 검색 중...");
        for(int i=0;i<=board[0].length-expectSize; i++){
            for(int j=0;j<=board.length-expectSize; j++){
                if(isSquare(expectSize, board, i,j)){
                    System.out.println("i :"+i+", j : "+j +" 에서 정사각형이 발견되었습니다.");
                    return true;
                }
            }
        }

        return false;
    }

    private boolean isSquare(int size, boolean [][]board, int x, int y){
        for(int i=x;i< x+size ;i++){
            for(int j=y;j< y+size ;j++){
                if(!board[i][j]) return false;
            }
        }
        return true;
    }


    /**
     * TODO 알고리즘의 효율을 높일려면 아예 다른 방법을 강구하거나,
     * true 로 시작하는 포지션들을 기억하고 처리하면서 검색해야 한다.
     * @param args
     */
    public static void main(String[] args)
    {
        TryHelloWorld test = new TryHelloWorld();
        char [][]board ={
                {'X','O','O','O','X'},
                {'X','O','O','O','O'},
                {'X','X','O','O','O'},
                {'X','X','O','O','O'},
                {'X','X','X','X','X'}
        };


        System.out.println(test.findLargestSquare(board));

    }
}