algospot 게임판 덮기 2 (문제 ID: BOARDCOVER2)

알고스팟 문제 링크: https://algospot.com/judge/problem/read/BOARDCOVER2

algospot.com :: BOARDCOVER2

게임판과 블럭이 입력으로 주어졌을때, 불규칙하게 부분적으로 채워진 게임판에 회전가능한 블럭을 놓을수 있는 최대값을 구하는 문제이다.

먼저 게임판에 채워진 부분을 1, 비어있는 부분을 0으로 표현한다. 그리고 주어진 블럭을 90도로 회전시켜가며 가능한 모양들을 좌표 형태로 저장한다.

이제 게임판에 빈칸들을 찾아내서 블록을 놓을 수 있으면 놓고 재귀호출 한다.

만약에 빈칸에 놓을 수 있는 블록의 모양이 없다면 해당 빈칸을 막아놓고 재귀호출한다. 그렇지 않으면 재귀호출을 했을때, 해당 빈칸에서 또 블록을 놓을 수 있는지 없는지 다시 계산을 반복하는식으로 무한루프에 빠진다.

이때 (현재 게임판에 놓은 블럭수) + (남은 빈칸들을 블럭크기로 나눈값) 이 지금까지 찾은 최적해보다 작다면 현재 탐색이 최적해가 될 수 없으므로 탐색을 그만둔다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20CombinatorialSearch/BOARDCOVER2.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1