02. BOARDCOVER

알고리즘문제해결전략 p159

문제

게임판 덮기 (문제ID:BOARDCOVER, 난이도 하)

알고스팟 링크

풀이

나는 2차원 입력값을 브루트포스로 뭔가 시뮬레이팅 하는 문제가 제-일 싫다.

그래서 원래 이 포스팅을 시작하면서 한번 풀었던 문제도 다시 풀려고 마음 먹었는데

이 문제는 그냥 옛날 코드를 조금 손보기만 했다.

아이디어는 좌상단에서 우하단으로 좌표를 이동시키면서 빈 칸이 있으면 재귀호출을 하는 방식으로

4가지의 블럭 모양의 기준을 좌상단 좌표로 맞추는게 핵심이다. (위나 왼쪽으로 삐져나가지 않는 방법으로)

이렇게 했을 경우에 항상 한번 지나온 좌표는 더 이상 신경 쓸 필요가 없기 때문에

한번의 DFS로 모든 경우의 수를 다 찾을 수 있다.

조금 깔끔하게 코드를 쓰기 위해서 '.' 과 '#'을 각각 True와 False로 치환해서 풀었다.

책에서는 배열에다가 블록의 모양을 구성하는 좌표를 미리 선언하는 방법을 사용했는데

코드가 조금 더 깔끔해 질 것 같긴 하지만 큰 이익이 있는 건 아닌것 같아서 수정하지 않았다.

리턴값을 더하는 방식이 아니라 전역변수에 더해주는 방식을 사용했다.

코드