[SW Expert] 5656. [모의 SW 역량테스트] 벽돌 깨기

생각

벽돌깨기 게임을 진행한다. 각 벽돌이 아닌칸은 0으로 주어지며, 각 벽돌이 가지고있는 숫자(1~9)는
자신의 숫자-1 만큼 상하좌우의 벽돌을 연쇄로 깰 수 있다. 공을 쏠수 있는 횟수(1~4)와 벽돌의 맵의 크기
w,h(2~12)가 주어졌을 때, 최대한 많은 벽돌을 깬 후 남은 벽돌의 개수를 출력하여라.

처음 생각

바로바로 풀 수 있는 문제들보다는 문제를 읽고 처음부터 생각을 해야하는 문제들이 나오는 추세인것 같다. 어떻게 벽돌을 많이 깰 수 있도록 공을 쏠 수 있을까?를 생각해보았다. 위에서 부터 한 줄씩 읽으면서 숫자가 큰게 나오면 없애주면 될까? 이건 반례가 너무 뻔히 보였다. 1 밑에 9같이 큰게 숨어있을 경우 안되기 때문이다. 그럼 어떻게 해봐야 할까..! 

▶우선 브루트포스(완전탐색)을 살펴보기로 했다. 공을 최대 4번 쏠 수있고, 맵의 열 크기도 최대 12이므로 12개중 1개를 고르는 것을 4번하면 총 12^4 = 약 3만 이 나오게된다. 즉 한 케이스 마다 최대 3만 번만 보면 되기 때문에 완전탐색이 가능하다.

다음 생각

최대 약 3만 번의 케이스의 시작마다 초기 상태를 가지고 있어야하므로 temp 배열을 만들어 주어 해당 케이스가 새로 시작할 때마다 처음 입력받은 배열의 값을 temp 배열로 복사해 주었다.

다다음 생각

완전 탐색을 하기로 정한 후는 문제에 정해진 조건대로 구현을 해주었다. 구현중 몇 가지를 잘 못생각하였다. 우선 최대 4개를 0~11 까지 봐주면 되므로 4중 반복문을 이용해서 공을 쏠자리를 정해준 후 폭탄 메소드로 해당 위치들을 넘겨주었다. 하지만 이렇게 할 경우 만약 n이 1이라면 불필요한 반복문의 작업이 되기 때문에 SET 자료구조를 이용해서 똑같은 인덱스가 들어온 경우는 메소드를 종료시켜 주었다.

다다다음 생각

해당 열의 위치를 전달 받으면 열의 위에서부터 0이 아닌 값을 찾아 해당 폭탄을 터트려주었다. 이때, 처음 시작은 딱 하나의 폭탄만 터뜨려야 하므로 break 문을 통해 해당 열을 종료해주었다.

다다다다음 생각

폭탄이 터지면서 상 하 좌 우로 자신이 가진 숫자 -1 만큼 주변 벽돌을 제거한다. 이를 구현할 때, 반복문의 index의 시작을 0부터 했었다가 테스트 케이스가 자꾸 틀려 틀린 것을 확인했다. 아래의 코드에서 해당 반복문을 0부터 시작하면 자기자신부터 포함시키기 때문에 벽돌이 제대로 제거되지 않았던 것이다. 1로 수정후 조건을 n-1이 아닌 n으로 바꿔주었다.

다다다다다음 생각

폭탄을 다 터트린 후, down() 메소드를 이용해서 열 별로 0이 아닌 값들을 밑으로 쌓아주었다. 그 후, n번의 공을 다 쏜후 count() 메소드를 호출하여 맵 전체를 살펴 0이 아닌 벽돌의 개수를 세어주었다.

방안

1) down()을 진행할 때, boolean 변수 flag를 사용해서 위쪽이 전부 0일 경우 해당 열의 down을 종료하였다.

2) 상 하 좌 우를 볼 때, 범위 조건을 추가하여 배열 범위를 벗어나는 것을 방지하였다.

3) 완전 탐색을 생각해내는게 어려웠던 문제 같다. 이후의 구현은 어떻게 완전 탐색 조건을 찾아줄 지, 언제 down을 호출할 지, 상 하 좌 우를 볼 때 인덱스 관리를 조심하면서 구현하였다.

4) 4개의 수를 받아 반복문으로 돌리기 위해서 배열을 사용하였는데, 수를 전달하지 말고 바로 배열로 넣어주어 배열을 전달해주면 더 깔끔할 것 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashSet; import java.util.StringTokenizer;   public class Solution{     static int n,w,h;     static int[][] arr;     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringBuilder sb = new StringBuilder();         int tc = Integer.parseInt(br.readLine());         for(int i=1;i<=tc;i++) {             StringTokenizer st = new StringTokenizer(br.readLine());             n = Integer.parseInt(st.nextToken());             w = Integer.parseInt(st.nextToken());             h = Integer.parseInt(st.nextToken());             arr = new int[h][w];             temp = new int[h][w];             for(int j=0;j<h;j++) {                 st = new StringTokenizer(br.readLine());                 for(int k=0;k<w;k++)                     arr[j][k] = Integer.parseInt(st.nextToken());             }             set = new HashSet<>();             result = Integer.MAX_VALUE;             solve();             sb.append("#"+i+" "+result+"\n");         }         System.out.print(sb);     }          private static void solve() {         // n은 최대 4번         // w최대 12 -> 12^4 = 20736 밖에 안된다. 완전 탐색 진행         for(int i=0;i<w;i++) {             for(int j=0;j<w;j++)                 for(int k=0;k<w;k++)                     for(int l=0;l<w;l++)                         toBomb(i,j,k,l);         }     }          static int[][] temp;     static HashSet<String> set;     private static void toBomb(int t1,int t2,int t3,int t4) {         // 새로운 경우를 위한 배열 초기화         initTemp();                  // n번의 케이스를 반복문으로 돌리기 위해서 배열 생성.         int[] tArr = new int[n];         switch(n) {         case 1:             tArr[0] = t1;             break;         case 2:             tArr[0] = t1; tArr[1] = t2;             break;         case 3:             tArr[0] = t1; tArr[1] = t2; tArr[2] = t3;             break;         case 4:             tArr[0] = t1; tArr[1] = t2; tArr[2] = t3; tArr[3] = t4;             break;         }         String t = "";         for(int i=0;i<n;i++)             t += tArr[i];                  // 이미 해본 케이스 일경우 return;         if(set.contains(t))             return;         set.add(t);         for(int i=0;i<n;i++) {             for(int j=0;j<h;j++) {                 if(temp[j][tArr[i]]!=0) {                     bomb(j,tArr[i],temp[j][tArr[i]]);                     break;                 }             }             // 블록을 다 뿌셨으면 빈칸 없애고 다음번 진행             down();         }         // 4번 다 뿌수고 남은 블록 세기         count();     }          private static void bomb(int x,int y,int n) {         temp[x][y] = 0;         // n==1이면 자기 자시만 0으로 만들고 return         if(n==1) return;         // 위쪽         for(int i=1;i<n;i++) {             if(x-i<0) break;             if(temp[x-i][y]!=0) {                 bomb(x-i,y,temp[x-i][y]);             }         }         // 왼쪽         for(int i=1;i<n;i++) {             if(y-i<0) break;             if(temp[x][y-i]!=0) {                 bomb(x,y-i,temp[x][y-i]);             }         }         // 오른쪽         for(int i=1;i<n;i++) {             if(y+i>=w) break;             if(temp[x][y+i]!=0) {                 bomb(x,y+i,temp[x][y+i]);             }         }         // 아래         for(int i=1;i<n;i++) {             if(x+i>=h) break;             if(temp[x+i][y]!=0) {                 bomb(x+i,y,temp[x+i][y]);             }         }     }          static int result;     private static void count() {         int cnt = 0;         for(int i=0;i<h;i++) {             for(int j=0;j<w;j++)                 if(temp[i][j]!=0) cnt++;         }         result = Math.min(result, cnt);     }          private static void down() {         // 한 열별로 행 끝에서 부터 쭉 보기         for(int i=0;i<w;i++) {             for(int j=h-1;j>=0;j--) {                 // 쭉 찾아 올라가다 0을 발견하면                 if(temp[j][i]==0) {                     // 그 위에를 살펴봐 0이 아닌 idx가 있으면 바꿔주고 그 idx를 0으로                     // 만약 위쪽에 0이 아닌게 없으면 바꿀 필요없으므로 해당 열 끝내기                     boolean flag = true;                     for(int k=j-1;k>=0;k--) {                         if(temp[k][i]!=0) {                             temp[j][i] = temp[k][i];                             temp[k][i] = 0;                             flag = false;                             break;                         }                     }                     if(flag) break;                 }             }         }     }          private static void initTemp() {         for(int i=0;i<h;i++) {             for(int j=0;j<w;j++)                 temp[i][j] = arr[i][j];         }     } } Colored by Color Scripter

cs