도입
이번엔 오답노트다. 하루에 몇 시간 안되긴 하지만 3일 정도 끙끙거리다가 결국 책의 뒷장을 넘겼다.
.
.
난이도 하
.
.
...
자괴감 들고 괴로워...
이전에 풀어보았던 완전 탐색 문제이다.
접근 자체는 좋았다. 반복문을 순환하며 덮을 수 있는 지점을 찾고, 덮을 수 있는 모양을 찾아 하나씩 채워가며 경우의 수를 세는 것.
우선 책의
답안 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOARDCOVER_ANSWER {
// https://algospot.com/judge/problem/read/BOARDCOVER
static int C;
static int H, W;
static int[][] board;
static int coverCnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
C = Integer.parseInt(br.readLine().replaceAll(" ", ""));
while (C-- > 0) {
String boardHW = br.readLine();
H = Integer.parseInt(boardHW.split(" ")[0]);
W = Integer.parseInt(boardHW.split(" ")[1]);
board = new int[H][W];
int coverableCnt = 0;
for (int i = 0; i < H; i++) {
String line = br.readLine();
for (int j = 0; j < W; j++) {
char point = line.charAt(j);
if (point == '#') {
board[i][j] = 1;
} else {
coverableCnt += 1;
}
}
}
if (coverableCnt % 3 != 0) {
sb.append(0).append("\n");
continue;
}
coverCnt = coverableCnt / 3;
sb.append(getAllCoverCount()).append("\n");
}
System.out.println(sb);
}
static int[][] dy = {{0, 1, 0}, {0, 0, 1}, {0, 1, 1}, {0, 1, 1}};
static int[][] dx = {{0, 0, 1}, {0, 1, 1}, {0, 0, 1}, {0, 0, -1}};
// 완성되었을때 모양을 저장해두어서 같은 모양으로 완성되지 않도록 해야한다.
static int getAllCoverCount() {
int y = -1, x = -1;
// 아직 채우지 못한 칸 중 제일 윗줄 왼쪽의 칸을 찾는다.
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (board[i][j] == 0) {
y = i;
x = j;
break;
}
}
if (y != -1)
break;
}
// 기저 사례 : 모든 칸을 채웠으면 1을 반환한다.
if (y == -1)
return 1;
int result = 0;
for (int type = 0; type < 4; type++) {
// 덮을 수 있다면 재귀 호출
if (cover(1, y, x, type))
result += getAllCoverCount();
// 덮었던 블록 치우기
cover(-1, y, x, type);
}
return result;
}
static boolean coverable(int y, int x) {
return y >= 0 && y < H && x >= 0 && x < W;
}
static boolean cover(int delta, int y, int x, int type) {
boolean coverable = true;
for (int i = 0; i < 3; i++) {
int yy = y + dy[type][i];
int xx = x + dx[type][i];
if (!coverable(yy, xx)) {
coverable = false;
break;
} else {
board[yy][xx] += delta;
if (board[yy][xx] > 1)
coverable = false;
}
}
return coverable;
}
}책에는 물론 CPP로 되어있으니 코드를 읽어보며 내 방식대로 짜보았다.
그 다음 내가 풀었던 방식
오답노트
public class BOARDCOVER {
// https://algospot.com/judge/problem/read/BOARDCOVER
static int C;
static int H, W;
static char[][] board;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
C = Integer.parseInt(br.readLine().replaceAll(" ", ""));
while (C-- > 0) {
String boardHW = br.readLine();
H = Integer.parseInt(boardHW.split(" ")[0]);
W = Integer.parseInt(boardHW.split(" ")[1]);
board = new char[H][W];
int coverableCnt = 0;
for (int i = 0; i < H; i++) {
String line = br.readLine();
for (int j = 0; j < W; j++) {
char point = line.charAt(j);
board[i][j] = point;
if (point == '.')
coverableCnt += 1;
}
}
if (coverableCnt % 3 != 0) {
sb.append(0).append("\n");
continue;
}
sb.append(cover(coverableCnt)).append("\n");
}
System.out.println(sb);
}
static int[][] dy = {{-1, 0}, {-1, 0}, {1, 0}, {1, 0}};
static int[][] dx = {{0, -1}, {0, 1}, {0, 1}, {0, -1}};
static int cover(int coverableCnt) {
if (coverableCnt == 0)
return 1;
int result = 0;
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
if (board[y][x] == '#')
continue;
for (int i = 0; i < 4; i++) {
int yy1 = y + dy[i][0];
int xx1 = x + dx[i][0];
int yy2 = y + dy[i][1];
int xx2 = x + dx[i][1];
if (coverable(yy1, xx1) && coverable(yy2, xx2)) {
board[y][x] = '#';
board[yy1][xx1] = '#';
board[yy2][xx2] = '#';
result += cover(coverableCnt - 3);
board[y][x] = '.';
board[yy1][xx1] = '.';
board[yy2][xx2] = '.';
}
}
}
}
return result;
}
static boolean coverable(int y, int x) {
return y >= 0 && y < H && x >= 0 && x < W && board[y][x] == '.';
}
}해결 포인트
물론 내가 풀지는 못했지만 핵심 포인트는 빈 칸 중 가장 위, 왼쪽(위가 먼저 고려되어야 함을 유의)을 채운다고 가정하며, 그보다 위, 왼쪽의 칸은 이미 채워져있다고 가정하는 것이다.
이러한 가정으로 순차적으로 도형을 채워나가면 앞서 채웠던 도형에 대해서는 다시 생각할 필요가 없으므로 같은 도형을 같은 자리에 채우는 경우를 중복해서 계산하는 경우를 배제할 수 있다.
오답 포인트
나의 코드에는 반복문을 돌며 막연히 덮을 수 있는 포인트에 덮을 수 있는 도형을 찾아 덮은 뒤 재귀 함수를 호출하고 있다.
여기에 기준이 있어야하는데, 빈 칸 중 가장 위, 왼쪽을 덮는다는 기준이 추가되었어야 한다.
이러한 기준이 없었기 때문에, 순서가 강제되지 않아 같은 모양으로 채우는 경우도 중복으로 계산하여 오답이 발생하였고, 심지어 문제의 예제 입력의 마지막 케이스는 무한 순환에 빠져 출력이 나오지도 않았다.
예를들어 반복문이 어떤 덮을 수 있는 포인트에 도달했을 때, 그 포인트를 덮고 재귀 함수를 호출하여 모든 빈 칸이 덮이는 경우를 계산하고 호출한 재귀 함수들이 종료되어도 반복문을 더 진행하여 다음 칸의 덮는 경우를 계산한다.
이미 재귀 호출한 함수들로 인해 계산된 다음 칸의 덮는 경우가 또다시 계산되는 것이다.
또한 이로인해, 덮을 수 있는 포인트에서 도형의 모양을 지정할 때 나같은 경우는 현재 포인트를 중앙으로 + 모양으로 4가지를 잡았는데, 이렇게하면 위에서 가정한 빈 칸 중 가장 위, 왼쪽을 덮는다는 가정이 꺠진다.
애초에 그런 가정이 없었기 때문에 이런식으로 모양을 지정했는데, 사실 모양을 잡은 것 자체가 문제가 아니라 앞선 기준이 없었기 때문이 문제였다.
문제 풀이할 때 중복을 제거하는 방법에 대해 고민하지 않은 것은 아닌데, 모든 포인트를 다 채웠을 때 BOARD가 어떤 모양인지를 비교해보아야 한다고만 생각했다.
결국 다 채울때까지는 반복문과 재귀 호출을 반복해야 하며, 애초에 발생한 무한 순환 문제는 해결하지 못한다.
그리고 모든 포인트를 다 채웠을때의 모양은 int[][] 자료형으로 각 지점마다 도형의 모양을 지정하는 방식으로 할 수 있다고까지는 생각했으나, 완성된 뒤에 이를 또 어떻게 저장해야할지에서 막혀서 꽤 많은 시간을 고민했던것 같다.
애초에 몇가지 경우의 수가 있는지 알지도 못하기 때문에 int[][][] 와 같은 3차원 배열로 지정하기도 애매하고, 이렇게 저장한다고 하더라도, 결국은 다 채워졌을 때 또다시 반복문을 순환하며 모든 요소를 검사해야하니 굉장히 비효율적이라고 생각해서 시도하지도 못했다.
완전 탐색 시에는 매 순환의 정확한 기준을 세우자.
오답노트 끝!
