• 발상:★★★, 구현:★★★
• Silver++ 이라는 언어로 프로그래밍하는 문제. 퍼즐문제에 가까운 문제이다.
• 처음 관찰해야 하는 것은, 현재 칸을 무조건 깨끗하게 만드는 것은 rF로 가능하다는 것. 이렇게 하면 처음에 먼지가 있든 없든 먼지를 없앨수 있지만, 로봇의 이후 위치가 현재칸이 될지 우측 칸이 될지는 알수 없다,
• 가로줄의 칸들을 0~n으로 번호를 붙이자. 0번칸에서 rFr을 한다면, 0번칸을 청소하고 1번칸 또는 2번칸에 위치하게 된다, 2번칸에 위치한 경우는 1번칸까지 청소가 된 상태이다. 따라서 여기서 또다시 rFr을 한다면 이제 1번칸까지도 확실히 청소가 되었음이 보장된다. 로봇의 위치는 2,3,4번칸중 하나에 있게 된다. 그렇다면, 0번칸에서 rFr 을 n번 한다면? n-1번 칸까지는 모두 청소가 되었고, 로봇은 n번 칸에 위치하게 된다. n이 마지막칸이므로 더 우측으로 갈수가 없기 때문이다. 이렇게 하면 길이 n짜리의 한 줄을 3*(n-1)번의 명령으로 마지막칸을 제외한 모든 칸을 청소할수 있다.
• 여기까지 발견하고 쉽게 든 알고리즘은 다음과 같았다.
  • 1)가로로 한줄을 오른쪽으로 이동하면서 다 청소한다.
  • 2)왼쪽으로 이동해서 원래 자리로 돌아온다.
  • 3)한칸 아래로 내려온다
  • 4)1~3을 16번 반복한다
  • 5)이제 각 행의 맨 오른쪽 칸에만 먼지가 존재할수 있다.
  • 6)오른쪽 끝열로 이동해서 세로방향으로 위로 이동하면서 청소한다.
  • 그러나 이 방식은 명령수 800 제한에 걸리게 된다. 1번과 2번을 하는데에 15*3 + 15 번이 걸리고, 이것을 16번 반복하면 (마지막에는 돌아오는 과정은 필요없긴 하지만) 이미 800번을 훌쩍 넘기게 된다.
• 다시 고민해서 개선한 방법은 지그재그 방법이었다
  • 1) 가로로 한줄을 오른쪽으로 이동하면서 다 청소한다.
  • 2) 아래로 한칸 내려오고 왼쪽으로 이동하면서 다 청소한다
  • 3) 아래로 한칸 내려오고 오른쪽으로 이동하면서 다 청소한다
  • 4) 2~3을 반복.
  • 5) 이제 맨 오른쪽 열과 맨 왼쪽열에 먼지가 존재한다.
  • 6) 오른쪽 열을 세로방향으로 위로 이동하면서 청소한다
  • 7) 현재칸의 먼지를 없앤다
  • 8) 왼쪽끝으로 이동
  • 9) 왼쪽 끝 열을 아래로 이동하면서 청소한다
  • 이렇게 하면 조금 줄어들기는 하지만, 여전히 800을 넘는다
• 사실 여기에서 운이 좋았으면 바로 정답을 떠올렸을텐데.. 운이 나쁘게도 머리가 다른쪽으로 돌아갔다.. ㅜㅜ
• 이 뒤에 한참 고민하던 방법은 이런것이었다.
  • 지그재그로 움직이되, 양 끝에 먼지를 냅두는 것이 아니라, 먼지를 모두 없애면서 움직인다.
  • 오른쪽 끝까지 움직인 뒤에, D로 내려오지 않고, dFd로 내려오면 윗 행의 먼지를 모두 없애고 아래로 내려올수 있다. 그러나 이 경우에는 현재 위치가 2번째 행이 될지 3번째 행이 될지 알수 없는 문제가 있는데.. dfd가 아니라 df이후에 UD를 해서 두번째 줄에 확실이 멈추도록 할수 있다.
  • 하지만, 3번째 행을 치운 뒤에 4번째 행에 멈추려면 dFUUUDDD 를 해야 하고, 아래쪽 행으로 갈수록 이 과정은 점점 더 길어진다
  • 이것을 조금 최적화해보겠다고 머리를 굴리던 것이.. 윗 행에서 일부러 먼지를 반드시 남겨놓는 것이다.
  • 현재 오른쪽 끝 칸에 있을때, 이곳에 먼지를 남기고 왼쪽으로 이동하는 것은 lFRFL 과 같은 방식으로 할수 있다. 이렇게 먼지를 남겨놓고 왼쪽으로 갔다가 아래 행으로 와서 다시 오른쪽 끝으로 오게 되면, 바로 윗칸에 먼지가 확실히 있는 상태가 된다. 이제 dFuuFdd로 윗칸의 먼지를 지우고 아래칸으로 정확히 이동할수 있다.
  • 이 방식을 사용하면 조금 더 줄일수 있으나 여전히 명령어수는 850에 가깝다..
  • 이걸 이제 더 최적화 하겠다고… 오른쪽 끝은 이방법으로 먼지를 싹 지우고 내려오고 왼쪽 끝은 먼지를 남기고 이동한 다음 마지막에 왼쪽 열을 다 지우는 방법을 적용했고, 먼지 마커를 매번 만드는 것보다 2번에 한번씩 만드는 것이 조금 더 줄일수 있어서 그렇게 했으나.. 최종적으로 약 815 명령의 벽을 넘을수 없었다.
• 이 접근법을 포기하고 다시 되돌아보니,, 그냥 처음 지그재그 방식을 떠올렸을때 비효율적인 부분이 있었다는 것을 알게 되었다. 첫번째 행을 두번 청소하게 되는 문제이다.. 처음에 시작을 첫행부터 청소하는 것이 아니라, 두번째 행부터 마지막 행까지 청소한 이후에, 오른쪽 끝열, 첫번째 행, 왼쪽 끝열 순서대로 테두리를 청소하면 아까 고민하던 것보다 훨씬 간단하게 처리된다. 이 방식으로 구현하면 795 명령이 된다.
• 최적해는 793명령인데, 이것은 똑같이 두번째 행부터 지그재그로 청소하되, 마지막부분을 가장 아래쪽행→ 가장 오른쪽열 → 가장 위쪽행 → 가장 왼쪽열 순서로 하지 않고, 반대 방향으로 가장 왼쪽열→가장 위쪽행→가장 오른쪽열→가장 아래쪽행 순서로 청소하는 것이다.

(다이아몬드 이상은 코드 생략)