[동적 계획법][비트 마스크][시도X] BLOCKGAME 블록게임

1. 완전 탐색

 

이 문제는 BOARDCOVER에서 문제를 풀었듯이 완전 탐색으로 해결 할 수 있다.

 

각 차례마다 사용 가능한 모든 블록들을 모든 위치에 넣어보면서 한번이라도

짝수 차례일때 블록을 못넣으면 함수를 종료시키면 된다.

 

2. 비트 마스크를 사용한 동적 계획법

 

이 문제는 주어진 게임판의 상태에 따라 승패가 좌우된다.

이전 까지의 블록의 배치와 지금이 누구 차례인지 알 필요 없다는 것이다.

 

게임판은 5*5배열로 '#' 과 '.' 두 상태가 있으므로 비트마스크로 

배열을 하나의 정수로 표현할 수 있다.

 

이 정수 하나로 메모이제이션이 가능해지고

완전 탐색에서 더욱 수행시간을 최적화 시킬 수 있다.

 

3. 비트마스크를 사용한 블록 배치 가능 유무성 판단

 

이 문제에서 블록의 형태는 L자 형과 | 형 ㅡ 형 이 있다. 

이 런 형태들을 돌리고 반전시킨것을 5*5배열에서 올 수 있는 모든 자리에

비트로 표현하고 전처리로 배열에 저장하면 더욱 직관적이고 깔끔한 코드를 작성할 수 있다.

 

비트마스크로 표현된 게임판과 & 연산 한번이면 바로 이곳에 블록을 놓을 수 있는지 판단할 수 있기 때문이다.

 

BLOCKGAME