BOARDCOVER2 문제 JAVA로 구현 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; } } } 6년 전
2개의 댓글이 있습니다. keith 가지치기로 높이, 폭 100짜리 (블럭이 4개를 차지하므로, 최대 깊이 25개), 최악의 경우(거의 모든게 비어있을때) 한 깊이에서 블럭을 놓을 수 있는 방법이 대략 100X100X4는 될거 같은데요.. 아무리 생각해도, 제한시간 2초내에 해결될거로 보이진 않습니다. 6년 전 link JungSol2 블럭의 크기는 문제에서 주어지구요, 한 깊이에서 블럭을 놓을 수 있는 방법은 최대 5가지가 아닐까요? 메소드를 한번 호출할때마다 가장 왼쪽상단의 비어있는 지점을 찾아서 블럭을 4방향으로 돌려서 각각 놓아보거나 블럭을 놓지 않는, 총 5가지의 행동을 할 수 있습니다. 6년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
JungSol2
안녕하세요. BOARDCOVER2문제를 Java를 이용해서 푸는데 가지치기를 적용해도 시간초과가 발생하네요. 아무리 로직을 봐도 잘못된게 없어보이는데 며칠동안 고민하다가 질문게시판에 올려봅니다. 자바라서 느린걸까요 제 로직에 문제가 있는걸까요?
6년 전