[algospot] 알고스팟 BOARD COVER [자바]

문제

H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.

입력

력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, . 는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.

출력

한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

예제 입력

3 
3 7 
#.....# 
#.....# 
##...## 
3 7 
#.....# 
#.....# 
##..### 
8 10 
########## 
#........# 
#........# 
#........# 
#........# 
#........# 
#........# 
########## 

예제 출력

0
2

1514

풀이 방법

메소드 설명.

•  isPossibleCase(가능한 케이스 판단 메소드)  ; L 모양이 2차배열에 들어갈 수 있는지 없는지 판단. 여기서 지역변수 int x는 case를 구분하기 위해 임의로 값을 넣어준것임.  (인덱스의 값이"." 일 때만 가능)
•  paintCaseA,B,C,D (가능하다면 케이스의 값을 벼꿔주는 메소드) : 4가지 경우에 있어서 가능한 경우가 있다면  인덱스 값이 " . "이었던 칸을 "#"으로 채워준다.
• nextRowCol (채워졌다면 다음 행, 열로 이동하고 callback 재귀함수수를 호출하거나 이동할 필요가 없다면 return하는 메소드) : checkArray를 호출해 return 값이 true라면 Result(경우의 수)값을 +1 시켜준다. 
• checkArray : 배열의 값이 모두 "#"으로 바뀌었는지 판단하는 메소드
• callback : 이 문제에 핵심이라고 할 수 있는 재귀함수. 

이해하기 어려울 수도 있어 이 부분을 글로 표현하자면 ,

if (isPossibleCase(row, column, 1, inputArray)) {
copiedArray = arrayCopy(inputArray);
paintCaseA(row, column, copiedArray);
nextRowCol(row, column, copiedArray);
}

만약 매개변수 x의 값이 1을 가진 경우라면 (케이스 A[┌]의 경우) (row, column은 처음엔 0.0부터 시작, inputArray는 사용자가 입력한 배열)
사용자가 입력한 배열의 모양을 copiedArray에 담아 놓는다. callback함수가 return 된 후에도 같은 모양의 배열에서 다른 경우의 수를 판단할 수 있게 하기 위함이다.
케이스 A의 인덱스 값을 "#"으로 바꾸고(paintCaseA),
다음 행과 열로 이동한 다음 재귀함수 호출한다(nextRowCol)는 뜻이다.

이와 같이 계속 재귀함수가 호출되면서 총 경우의 수를 계산한다.


프로그래밍 입문이라 코드가 정리되진 않았지만.. 혹시 누군가 도움이 될수도 있다는 생각에 공유한다.
코드는 아래와같다.

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 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213

package algospot; import java.util.Scanner; public class BoardCover {     public static int HEIGHT = 0; // 높이(행)     public static int WIDTH = 0; // 너비(열)     public static int TOTALNUM = 0; // height*width     public static int RESULT = 0; // 경우의 수     public static void main(String[] args) {         // 1. 사용자에게 입력받음         Scanner scan = new Scanner(System.in);         int testCount = scan.nextInt();         for (int test = 0; test < testCount; test++) {             int height = scan.nextInt();             HEIGHT = height;             int width = scan.nextInt();             WIDTH = width;             TOTALNUM = height * width;             String[][] inputArray = new String[height][width];             for (int row = 0; row < height; row++) {                 String dd = scan.next();                 for (int column = 0; column < width; column++) {                     inputArray[row][column] = String.valueOf(dd.charAt(column));                 }             }             callBack(0, 0, inputArray);             System.out.println(RESULT);             RESULT = 0;         }     }     // 배열 출력 모양     private static void printInputArray(String[][] inputArray) {         for (int row = 0; row < HEIGHT; row++) {             for (int column = 0; column < WIDTH; column++) {                 System.out.print(inputArray[row][column]);             }             System.out.println("");         }     }     // 0.0의 인덱스를 시작으로 callBack     private static void callBack(int row, int column, String[][] inputArray) {         if ("#".equals(inputArray[row][column])) {             nextRowCol(row, column, inputArray);         }         String[][] copiedArray;         if (isPossibleCase(row, column, 1, inputArray)) {             copiedArray = arrayCopy(inputArray); //처음 복사된 배열을 가짐 (사용자가 입력한 배열)             paintCaseA(row, column, copiedArray);// . 의 부분을 ┌ 모양으로 #으로 바꿈              nextRowCol(row, column, copiedArray);//callback이 여기서 호출됨. 이때 들어가는 배열은 paint된 배열.          }         if (isPossibleCase(row, column, 2, inputArray)) {             copiedArray = arrayCopy(inputArray); //처음 복사된 배열             paintCaseB(row, column, copiedArray);             nextRowCol(row, column, copiedArray);         }         if (isPossibleCase(row, column, 3, inputArray)) {             copiedArray = arrayCopy(inputArray);             paintCaseC(row, column, copiedArray);             nextRowCol(row, column, copiedArray);         }         if (isPossibleCase(row, column, 4, inputArray)) {             copiedArray = arrayCopy(inputArray);             paintCaseD(row, column, copiedArray);             nextRowCol(row, column, copiedArray);         }         return;     }     private static void nextRowCol(int row, int column, String[][] inputArray) {         if (checkArray(inputArray)) {             RESULT++;             return;         }                  //row가 마지막 행이면 return.          //우리가 계산하려고 하는 블럭은 ㄴ 모양 이기 때문에 2*2 행렬만 취급한다. 따라서 마지막 행은 계산할 필요가 없다.          if (row == HEIGHT - 1) {             return;         }                  //column이 width-2일때          //위와 같은 논리로 마지막 열에는 들어가지 않기 때문에 계산할 필요 없다.          if (column == WIDTH - 2) {             if (row + 1 == HEIGHT - 1) { //row가 마지막 행이면 return                 return;             }                          callBack(row + 1, 0, inputArray);//행이 한줄 내려감                      } else if (column < WIDTH - 1) {                              callBack(row, column + 1, inputArray); //열이 한칸 이동함         }     }     //┌ ┐└ ┘패턴이 가능한지 판단( 값이 "." 인 곳만 가능하다)     public static boolean isPossibleCase(int row, int column, int x, String[][] inputArray) {         boolean case_A = inputArray[row][column].equals(".") && inputArray[row][column + 1].equals(".")                 && inputArray[row + 1][column].equals(".") == true;         boolean case_B = inputArray[row][column].equals(".") && inputArray[row][column + 1].equals(".")                 && inputArray[row + 1][column + 1].equals(" .") == true;         boolean case_C = inputArray[row][column].equals(".") && inputArray[row + 1][column + 1].equals(".")                 && inputArray[row + 1][column].equals(".") == true;         boolean case_D = inputArray[row][column + 1].equals(".") && inputArray[row + 1][column].equals(".")                 && inputArray[row + 1][column + 1].equals(".") == true;         // 1         if (x == 1 && case_A) {             return true;         }         // 2         if (x == 2 && case_B) {             return true;         }         // 3         if (x == 3 && case_C) {             return true;         }         // 4         if (x == 4 && case_D) {             return true;         }         return false;     }     //┌ ┐└ ┘ 가 가능하면 . 을 # 으로 변경      //caseA     public static String[][] paintCaseA(int row, int column, String[][] inputArray) {         inputArray[row][column] = "#";         inputArray[row][column + 1] = "#";         inputArray[row + 1][column] = "#";         // System.out.println("A경우 색칠! 결과는 : ");         // printInputArray(inputArray);         return inputArray;     }          //caseB     public static String[][] paintCaseB(int row, int column, String[][] inputArray) {         inputArray[row][column] = "#";         inputArray[row + 1][column + 1] = "#";         inputArray[row][column + 1] = "#";         // System.out.println("B경우 색칠! 결과는 : ");         // printInputArray(inputArray);         return inputArray;     }          //caseC     public static String[][] paintCaseC(int row, int column, String[][] inputArray) {         inputArray[row][column] = "#";         inputArray[row + 1][column] = "#";         inputArray[row + 1][column + 1] = "#";         // System.out.println("C경우 색칠! 결과는 : ");         // printInputArray(inputArray);         return inputArray;     }     //caseD     public static String[][] paintCaseD(int row, int column, String[][] inputArray) {         inputArray[row][column + 1] = "#";         inputArray[row + 1][column] = "#";         inputArray[row + 1][column + 1] = "#";         // System.out.println("D경우 색칠! 결과는 : ");         // printInputArray(inputArray);         return inputArray;     }     //배열이 #으로 다 찼는지 판단     private static boolean checkArray(String[][] inputArray) {         int count = 0;         for (int row = 0; row < HEIGHT; row++) {             for (int column = 0; column < WIDTH; column++) {                 if (inputArray[row][column].equals("#")) {                     count++;                 }              }         }                  if (count == TOTALNUM) {             return true;         } else             return false;     } } Colored by Color Scripter

cs

코드 질문이나 다른 문의사항 모두 환영!

그럼...누군가에게 도움이되길 바라면서 오늘도 화이팅!!