[조합 탐색][시도x]BOARDCOVER2 게임판 덮기2
1. 완전 탐색
주어진 블록으로 빈 공간에 넣을 수 있는 최대 개수를 구하는 문제이다.
이 문제를 풀기 위해서는 일단 다음과 같은 함수가 필요할 것 같다.
- 블록들을 회전 시키는 함수.
- 왼쪽위에서부터 오른쪽아래까지 블록을 넣는지 않넣는지 , 블록을 넣을때 회전하는 케이스 까지
모든 경우를 세는 함수.
이 완전 탐색으로는 시간안에 못풀것 같다.
10*10 의 빈 공간이 있으면
최대 5^100번 함수가 실행 될것 같기 때문이다. (5가지 경우 수 선택 x 0 90 180 270에 100개의 칸)
물론 이것이 실제 돌아가면 훨씬 더 빨리 수행될것이다.
하지만 그래도 엄청나게 큰 수행시간 일 것이다.
2. 조합탐색 - 가지치기
단순 휴리스틱 함수를 구현하면 더욱 빨리 수행될 것 같다.
이 함수는 남은 칸의 수를 가지고 블록이 최대 얼마 생성될수 있는지를 짐작한다.
일단 다음과 같이 문제 조건의 제약을 없애 이 문제를 푸는 함수를 작성해보자.
1. 블록형태를 잘라서 직사각형 정사각형 으로 만든다.
2. 이 블록을 사용해서 왼쪽 위부터 오른쪽 아래까지 채울 수 있는 만큼 가로 세로 로 빈 곳을 채우자
3. 채울때는 검은 칸을 덮을 수 있다. (단 덮는 수를 최소화 해야함.)
아마 이 함수는 어느정도 조합들을 가지치기해 줄 것이다.
책에서는 가지치기를 다음과 같이 했다.
1. 블록을 분리=> 1개의 칸으로 이루어진 블록들
2. 남은 칸을 이것으로 채움.
== 남은칸의 개수 / 블록의 크기
확실히 이 가지치기는
항상 우리가 실제 놓을 수 있는 블록의 수 이상이기 때문에
답의 상한이 된다는 것은 명확하다.
- 알고리즘 문제해결 전략 427p