[알고스팟] BOARDCOVER - 게임판 덮기 (C++)

문제

algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

풀이

흰 칸들을 4가지 모양(회전하면 네 가지 모양이 나옴)으로 덮을 경우 가능한 경우 수를 구하는 문제.

해당 문제는 다음과 같이, 한 빈칸을 네 가지 경우로 채우는 재귀 함수를 구현한다.

 

4가지 경우의 블록, 빨간 부분이 현재 호출된 칸의 위치

 

 빨간 부분이 호출된 칸이고, 그 칸과 인접한 1,2번 블록을 채우는 네 가지 블록 모델이다.

 

 이렇게 네가지 경우 이외는 생각해 주지 않아도 되는 이유는 흰 칸의 위치를 찾는 함수는 현재 위치부터 column을 +1씩 증가시키며 찾도록 구현하기 때문이다. 따라서 빨간 칸의 위치가 호출되었다면 이전의 칸들은 모두 채워져 있는 것이므로 그 이후의 칸을 채우는 네 가지 경우로 분류한다.

 

blockModel에 해당 블록들의 1,2번 블록의 빨간 블록부터의 상대 위치 값을 넣어준다.

 

FindWhiteBlock을 통해 다음 흰블록을 찾고 찾았다면 true, 보드가 끝났다면 false를 반환한다. 이 함수를 구현할 때 else를 제대로 못 붙여서 한참을 오류와 씨름했다...

 

CountCoverWhite에서는 4가지 경우를 돌면서 경곗값과 블록이 놓일 칸이 흰색인지 확인한다. 만약 블록을 둘 수 있다면 현재 총 흰 칸의 개수를 -3해 주고 검은 칸을 채워준 뒤 다음 흰 칸을 찾아 재귀 호출해준다. 호출이 끝나면 변경한 값들은 복구시켜준다. 구현할 때 흰 칸이 모두 채워진 경우 바로 1을 반환시켜서, whiteNum을 복구시켜주지 못해 또 한참 헤맸다... 전역 변수를 쓰는 것을 조심해야 하는 이유를 뼈저리게 느꼈다.

 

물론 흰 칸의 개수가 3의 배수가 아닌 경우와 흰 칸이 없는 경우는 바로 0을 출력시킨다.

 

풀이는 빨리 생각했지만 코드로 구현한 것이 너무 조잡한 느낌이다. 만약 코드가 읽기 힘들다면 죄송합니다 ㅠㅠ

 

결과: 0ms

 

코드