H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.
완전 탐색으로 접근하였습니다. DFS와 비슷한 방식으로 풀면 됩니다. L자 모양의 칸을 덮기 위해서 총 4가지의 덮는 방법의 수가 나오게됩니다. 이를 coverType이라고 생각해보겠습니다.
총 4가지의 모양으로 나올 수 있습니다. 해당 모양으로 다 덮으면서 모든 칸이 1일경우 모두 덮힌 구간이므로 개수 1개를 세어주고 덮은 후 계산이 끝나면 원래대로 빼주면 됩니다.
경우의 수는 무척 많습니다만, 덮는 위치, 순서를 강제화 해주면 크게 많이 경우의 수가 나오지 않는다는 것을 알 수 있습니다.
4. 풀이 방법
칸을 덮고, 치울 수 있는 함수를 만들어줘야 합니다. L자는 총 3칸이므로 3번 반복합니다. coverType으로 L자 모양의 보드를 채우며 만약 범위를 벗어나거나 중복되는 경우가 발생하면 False를 return합니다. (덮히지 않으므로)
칸을 덮는 함수를 작성합니다. 시작 위치를 왼쪽 위부터 차례대로 탐색합니다. (순서의 강제) 만약 전부 덮혀있다면 1을 리턴해줍니다.
시작 위치로부터 4가지의 타입으로 덮어보고 덮힌다면 계속 덮기위해 칸을 덮는 함수를 재귀하고 덮히지 않는다면 덮힌 부분을 다시 빼줍니다. 만약 하나도 덮히지 않는다면 0을 반환 해줄 것입니다.
