풀이 방법
메소드 설명.
- 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;
}
}
| cs |
코드 질문이나 다른 문의사항 모두 환영!
그럼...누군가에게 도움이되길 바라면서 오늘도 화이팅!!
