문제 설명
H x W 크기의 게임판과 한 가지 모양의 블록이 여러 개 있다. 게임판에 가능한 한 많은 블록을 올려놓고 싶은데,
게임판은 검은 칸과 흰칸으로 구성된 격자 모양을 하고 있으며 이 중에서 흰 칸에만 블록을 올려놓을 수 있다.
이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 격자에 어긋나게 덮거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안된다.
시간 및 메모리 제한
프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T(T<100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 게임판의 크기 H , W(1<= H, W <= 10), 그리고 블록의 모양을 나타내는 격자의 크기 R, C(1<= R, C <= 10) 이 주어집니다. 다음 H줄에는 각각 W글자의 문자열로 게이만의 정보가 주어집니다. 문자열의 각 글자는 게임판의 한 칸을 나타내며, #은 검은 칸, 마침표는 흰 칸을 의미합니다. 다음 R줄에는 각 C 글자의 문자열로 블록의 모양이 주어집니다. 이 문자열에서 #은 블록의 일부, 마침표는 빈 칸을 나타냅니다.
출력
각 테스트 케이스마다 게임판에 놓을 수 있는 최대 블록의 수를 출력합니다.
풀이
먼저 완전 탐색으로부터 문제 해결을 시도해본다. 이전의 BLOCKGAME1 예제에서는 게임판 위에 놓을 블록의 형태가 정해져 있었기에 고정된 경우의 수에 대해서만 탐색을 실행하면 되었었지만,
이 문제는 블록의 형태가 정해져 있지 않기 때문에 이러한 접근은 불가능하다. BLOCKGAME1과 같이 게임판의 맨 왼쪽 위부터 차례로 블록을 놓는 것으로 탐색의 순서를 강제하되, 블록을 동서남북
4가지 방향으로 회전시켜 각 경우에 대해 모두 탐색을 실행해 보아야 할 것 같았다. 각각의 회전된 블록에 대해 맨 왼쪽 위에 있는 검은 칸의 상대좌표를 (0,0)이라고 하고, 나머지 검은 칸의 상대좌표를 구해
배열에 저장해 놓는 전처리 과정을 거쳐야 한다.
static ArrayList<String> rotate(ArrayList<String> block) {
ArrayList<String> ret = new ArrayList<>();
for(int i = 0 ; i < block.get(0).length() ; i++) {
String str = "";
for(int j = block.size() - 1 ; j >= 0 ; j--) {
str += block.get(j).charAt(i);
}
ret.add(str);
}
return ret;
} 이 함수는 String을 원소로 갖는 List에 저장된 블록을 파라미터로 받아 시계방향으로 90도 회전한 결과를 리턴하는 함수이다.
예를 들어 원래의 블록과 회전한 후의 블록의 형태는 다음과 같다.
.#. .#.
### --> .##
..# ##.그리고 이 함수를 이용해 처음 입력으로 받은 블록을 네 가지 방향으로 회전하여 얻은 결과를 저장하는 함수를 작성한다.
static void generateRotations(ArrayList<String> block) {
rotations.clear();
for(int rot = 0 ; rot < 4 ; rot++) {
rotations.add(new ArrayList<>());
int originY = -1, originX = -1;
for(int i = 0 ; i < block.size() ; i++){
for(int j = 0 ; j < block.get(0).length() ; j++){
if(block.get(i).charAt(j) == '#') {
if(originY == -1) {
originY = i;
originX = j;
}
rotations.get(rot).add(new Pair<>(i- originY, j - originX));
}
}
}
block = rotate(block);
}
blockSize = rotations.get(0).size();
}이렇게 하면 모든 전처리 과정이 끝나고, 이제부터 본격적인 완전 탐색을 시작할 수 있다.
static int solve() {
best = 0;
// covered 배열 초기화
for(int i = 0 ; i < height ; i++) {
for(int j = 0 ; j < width ; j++) {
covered[i][j] = (board.get(i).charAt(j) == '#' ? 1 : 0);
}
}
// 최적해 찾는 함수
search(0);
return best;
}최적해 best를 반환하는 함수 solve를 작성하고, 여기서 실제로 탐색을 진행하며 전역 변수 best를 그때그때 update 해주는 search() 함수를 불러온다.
이러한 구조로 함수를 작성하면 나중에 pruning하기가 쉬워질 것이라고 예상할 수 있다.
조합탐색을 이용해 푸는 문제이기 때문에 단순히 완전 탐색 알고리즘만으로는 제한시간 내에 문제가 풀리지 않을 것이라고 생각했다. 그래도
문제를 정확히 풀고는 있는지 확인하기 위해 현재 상태에서 인풋을 넣어봤더니, 몇 분이 지나도 프로그램은 답을 내놓지 않는다...
화장실을 다녀와도 커서만 깜빡일 뿐이었다.. 블록을 rotate했을 때 모양이 중복되는 경우를 제거한다면 그나마 실행시간이 빨리지긴 하겠지만 우선 pruning을 적용해 보기로 했다.
이 문제에서 생각할 수 있는 optimistic heuristic은 단순히 게임판 위의 남은 빈칸의 수를 블록의 칸 개수로 나누는 것이다. 굉장히 문제를 과대평가하는 heuristic이긴 하지만, 이것만으로도 커다란 이득을 볼 수 있을 것이라고 책은 설명한다.
static void search(int numOfPlaced) {
int empty = 0;
for(int i = 0 ; i < height ; i++) {
for(int j = 0 ; j < width ; j++) {
if(covered[i][j] == 0) empty++;
}
}
if(numOfPlaced + Math.ceil(empty / (float)blockSize) < best) return;
//...생략search 함수의 맨 위에 이와 같이 optimistic한 heuristic value를 이용한 해의 값이 현재까지 구한 최적해보다 작으면
아무일도 하지 않고 리턴하도록 했다.
2
5 10 3 3
..........
..........
..........
..........
..........
.#.
###
..#
8
4 7 2 3
##.##..
#......
#....##
#..####
###
#..
3
Process finished with exit code 0이제는 프로그램이 빠른 시간 내에 답을 구할 수 있게 되었다.
유념할 점들
1. 전처리 과정과 실제 탐색 수행 과정을 적절히 선정, 명확한 분리
실제 탐색 과정에서 필요한 데이터들은 최대한 전처리 과정으로 분리하여 구하도록 하자.
로직과 데이터를 분리하기 위한 효율적인 과정이라고 생각된다.
2. 자료를 저장하기 위한 적절한 자료형 선택
자료형을 어떻게 선택하냐에 따라 프로그램의 실행시간은 크게 달라지지 않겠지만,
적절한 자료형의 선택은 쓰기 쉽고, 읽기 쉬운 코드를 만들어준다고 생각한다.
