[조합 탐색][시도x]BOARDCOVER2 게임판 덮기2

1. 완전 탐색

 

주어진 블록으로 빈 공간에 넣을 수 있는 최대 개수를 구하는 문제이다.

 

이 문제를 풀기 위해서는 일단 다음과 같은 함수가 필요할 것 같다.

 

- 블록들을 회전 시키는 함수.

- 왼쪽위에서부터 오른쪽아래까지 블록을 넣는지 않넣는지 , 블록을 넣을때 회전하는 케이스 까지 

  모든 경우를 세는 함수.

 

이 완전 탐색으로는 시간안에 못풀것 같다.

 

10*10 의 빈 공간이 있으면

최대 5^100번 함수가 실행 될것 같기 때문이다. (5가지 경우 수 선택 x 0 90 180 270에 100개의 칸)

 

물론 이것이 실제 돌아가면 훨씬 더 빨리 수행될것이다.

하지만 그래도 엄청나게 큰 수행시간 일 것이다.

 

2. 조합탐색 - 가지치기

 

단순 휴리스틱 함수를 구현하면 더욱 빨리 수행될 것 같다.

 

이 함수는 남은 칸의 수를 가지고 블록이 최대 얼마 생성될수 있는지를 짐작한다.

 

일단 다음과 같이 문제 조건의 제약을 없애 이 문제를 푸는 함수를 작성해보자.

 

1. 블록형태를 잘라서 직사각형 정사각형 으로 만든다.

2. 이 블록을 사용해서 왼쪽 위부터 오른쪽 아래까지  채울 수 있는 만큼 가로 세로 로 빈 곳을 채우자

3. 채울때는 검은 칸을 덮을 수 있다. (단 덮는 수를 최소화 해야함.)

 

아마 이 함수는 어느정도 조합들을 가지치기해 줄 것이다.

 

책에서는 가지치기를 다음과 같이 했다.

 

1. 블록을 분리=> 1개의 칸으로 이루어진 블록들

2. 남은 칸을 이것으로 채움.

 

== 남은칸의 개수 / 블록의 크기

 

확실히 이 가지치기는 

항상 우리가 실제 놓을 수 있는 블록의 수 이상이기 때문에

답의 상한이 된다는 것은 명확하다.

 

 

- 알고리즘 문제해결 전략 427p

BOARDCOVER2