algospot 게임판 덮기 (문제 ID: BOARDCOVER) c++

algospot 문제링크: https://www.algospot.com/judge/problem/read/BLOCKGAME

algospot.com :: BLOCKGAME

일정부분 채워져있는 게임판이 입력으로 주어졌을때 L자모양의 3칸짜리 블록으로 주어진 게임판을 채울수 있는 경우의 수를 구하는 문제입니다.

주어진 게임판에 알맞은 모양으로 블록을 놓고 그 모양의 게임판을 재귀호출하는 방법으로 완전탐색을 이용해 문제를 풀수있습니다.

이때 주의할점은 블록을 놓는 순서에 따라 똑같은 경우를 중복해서 셀수있다는 것입니다.

이를 방지하기 위해서 좌측에서 우측으로 상단에서 하단으로 순서대로 탐색합니다.

탐색중 빈칸을 만나면 블록의 각 모양을 대입하고 놓을수 있으면 놓고 재귀호출합니다.

이문제의 까다로운 점은 L자 모양의 블록을 90도 돌려가면서 나올수 있는 여러가지 모양의 블록을 두개의 2차원배열로 표현하여 하나씩 대입해봐야 된다는 겁니다.

하지만 경우의 수가 4가지 밖에 안되기때문에 충분히 수동으로 입력가능합니다.

 

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/6.%20brute-force/BOARDCOVER.cpp

GitHub - sbl133/JongmanBook

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

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