0과 1의 쉼터

문제 algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 algospot.com 풀이 버튼을 누르는 순서는 중요하지 않지만, 4번 누르면 시계가 원래대로 돌아오기 때문에 O(4^10)인 완전 탐색이 가능하다. 우선 버튼을 눌렀을 때 시간이 변하는 시계들을 다음과 같이 정리해주자. 각 배열의 첫번째 요소는 배열의 길이를 의미한다. 버튼을 누르는 횟수는 4회 미만이므로 버튼을 눌렀을 때 시계를 바로 업데이트 하는 것이 아닌 다음 버튼을 누르는 Recursive Call을 해서 분기를 ..

문제 algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 풀이 주어지는 보드의 빈 공간에 3칸으로 만들어진 'ㄴ' 모양의 블럭으로 전부 다 덮는 경우의 수를 구하는 문제다. 한 위치에서 12개의 경우의 수가 주어지지만, 블럭을 순차적으로 놓기 때문에 한 방향에 대해서만 생각해도 충분하다. 위/왼쪽을 기준으로 채운다고 가정했을 때 필요한 블럭은 아래와 같다. 여러번 사용해야하므로 미리 만들어두자. 가장 왼쪽 위 부터 비어있는 공간을 찾으며 dfs를 진행하자. 블럭을 다 채웠다면 못찾고 종료하므..