728x90
문제
algospot.com :: BOARDCOVER
게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이
algospot.com
풀이
주어지는 보드의 빈 공간에 3칸으로 만들어진 'ㄴ' 모양의 블럭으로 전부 다 덮는 경우의 수를 구하는 문제다.
한 위치에서 12개의 경우의 수가 주어지지만, 블럭을 순차적으로 놓기 때문에 한 방향에 대해서만 생각해도 충분하다.
위/왼쪽을 기준으로 채운다고 가정했을 때 필요한 블럭은 아래와 같다.
여러번 사용해야하므로 미리 만들어두자.
가장 왼쪽 위 부터 비어있는 공간을 찾으며 dfs를 진행하자. 블럭을 다 채웠다면 못찾고 종료하므로 예외처리 해주자.
4가지 종류의 블럭을 하나씩 덮어보며( cover(cur, type, 1) ) 덮어진다면, 이어서 블럭을 덮을 수 있는지 확인해보자.
만약 다 덮지 못한다면 다시 걷어내자
소스코드
728x90
'PS > Algospot (for. 알고리즘 문제해결 전략)' 카테고리의 다른 글
| [Algospot] CLOCKSYNC [C/C++] (0) | 2024.03.15 |
|---|