BOARDCOVER2 문제 JAVA로 구현

  • JungSol2
    JungSol2

    안녕하세요. BOARDCOVER2문제를 Java를 이용해서 푸는데 가지치기를 적용해도 시간초과가 발생하네요. 아무리 로직을 봐도 잘못된게 없어보이는데 며칠동안 고민하다가 질문게시판에 올려봅니다. 자바라서 느린걸까요 제 로직에 문제가 있는걸까요?

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.StringTokenizer;
    
    public class Main {
        static boolean[][] board, block; //true면 채워져있고 false면 비어있는것 
        static List<List<int[]>> settingCase;
        static int blockWidth, blockHeight, maxBlockCount;
        public static void main(String[] args) throws IOException {
            Main main = new Main();
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            int cases = Integer.parseInt(bufferedReader.readLine());
            while(cases-- > 0) {
                maxBlockCount = 0;
                StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
                board = new boolean[Integer.parseInt(stringTokenizer.nextToken())][Integer.parseInt(stringTokenizer.nextToken())];
                int blockWidth = Integer.parseInt(stringTokenizer.nextToken()), blockHeight = Integer.parseInt(stringTokenizer.nextToken()), blanckCount = 0;
                for(int i = 0; i < board.length; i++) {
                    char row[] = bufferedReader.readLine().toCharArray();
                    for(int j = 0; j < board[i].length; j++) {
                        board[i][j] = row[j] == '#';
                        if(row[j] == '.') {
                            blanckCount++;
                        }
                    }
                }
                block = new boolean[blockWidth][blockHeight];
                for(int i = 0; i < block.length; i++) {
                    char row[] = bufferedReader.readLine().toCharArray();
                    for(int j = 0; j < row.length; j++) {
                        block[i][j] = row[j] == '#';
                    }
                }
                main.makeSettingCase();
                main.countMaxBlock(0, 0, 0, blanckCount);
                System.out.println(maxBlockCount);
            }
        }
    public void makeSettingCase() {
            settingCase = new ArrayList<>();
            for(int i = 0; i < 4; i++) {
                List<int[]> setting = new ArrayList<>();
                int leftTop[] = {-1,-1};
                for(int j = 0; j < block.length; j++) {
                    for(int k = 0; k < block[j].length; k++) {
                        if(block[j][k]) {
                            if(leftTop[0] == -1) {
                                leftTop[0] = j;
                                leftTop[1] = k;
                            }
                            setting.add(new int[]{j-leftTop[0], k-leftTop[1]});
                        }
                    }
                }
                boolean isSame = !settingCase.isEmpty();
                for(int j = 0; j < settingCase.size() && isSame; j++) {
                    for(int k = 0; k < setting.size() && isSame; k++) {
                        isSame = isSame && settingCase.get(j).get(k)[0] == setting.get(k)[0]
                                && settingCase.get(j).get(k)[1] == setting.get(k)[1];
                    }
                }
                if(!isSame) settingCase.add(setting);
                rotateBlock();
            }
        }
    
        public void rotateBlock() {
            boolean[][] rotatedBlock = new boolean[block[0].length][block.length];
            for(int i = 0; i < rotatedBlock.length; i++) {
                for(int j = 0; j < rotatedBlock[0].length; j++) {
                    rotatedBlock[i][j] = block[block.length-1-j][i];
                }
            }
            block = rotatedBlock;
        }
        public void countMaxBlock(int i, int j, int currentBlockCount, int remainedBlanckCount) {
            if(currentBlockCount + remainedBlanckCount / settingCase.get(0).size() <= maxBlockCount) return;
            boolean cover = false;
            for(; i < board.length && !cover; i++) {
                j = 0;
                for(; j < board[i].length && !cover; j++) {
                    if(!board[i][j]) {
                        cover = true;
                        for(List<int[]> settings : settingCase) {
                            if(canSet(settings, i, j)) {
                                setBlock(settings, i, j, true);
                                countMaxBlock(i, j+1, currentBlockCount+1, remainedBlanckCount-settingCase.get(0).size());
                                setBlock(settings, i, j, false);
                            }
                        }
                        board[i][j] = true;
                        countMaxBlock(i, j+1, currentBlockCount, remainedBlanckCount-1);
                        board[i][j] = false;
                    }
                }
            }
            if(!cover) maxBlockCount = Math.max(maxBlockCount, currentBlockCount);
        }
    
        private boolean canSet(List<int[]> settings, int cX, int cY) {
            boolean canSet = true;
            for(int i = 0; i < settings.size() && canSet; i++) {
                int x = settings.get(i)[0];
                int y = settings.get(i)[1];
                canSet = canSet && cX+x >= 0 && cX+x < board.length 
                        && cY+y >= 0 && cY+y < board[0].length
                        && !board[cX+x][cY+y];
            }
            return canSet;
        }
    
        private void setBlock(List<int[]>  settings, int cX, int cY, boolean setMode) {
            for(int[] set : settings) {
                board[cX+set[0]][cY+set[1]] = setMode;
            }
        }
    }
    

    1주 전
2개의 댓글이 있습니다.
  • keith
    keith

    가지치기로 높이, 폭 100짜리 (블럭이 4개를 차지하므로, 최대 깊이 25개), 최악의 경우(거의 모든게 비어있을때) 한 깊이에서 블럭을 놓을 수 있는 방법이 대략 100X100X4는 될거 같은데요.. 아무리 생각해도, 제한시간 2초내에 해결될거로 보이진 않습니다.


    1주 전 link
  • JungSol2
    JungSol2

    블럭의 크기는 문제에서 주어지구요, 한 깊이에서 블럭을 놓을 수 있는 방법은 최대 5가지가 아닐까요? 메소드를 한번 호출할때마다 가장 왼쪽상단의 비어있는 지점을 찾아서 블럭을 4방향으로 돌려서 각각 놓아보거나 블럭을 놓지 않는, 총 5가지의 행동을 할 수 있습니다.


    1주 전 link
  • 댓글을 남기시려면 로그인하세요.