BOJ 24680 Silver-16
BOJ 24680 Silver-16
문제 내용
16x16 크기의 사각 격자의 맨 왼쪽 위 칸에 청소기가 놓여 있습니다. 각 칸은 먼지가 있는 상태이거나 먼지가 없는 상태일 수 있습니다.
청소기는 다음과 같은 명령을 수행할 수 있습니다.
UDLR: 상하좌우로 1칸 움직입니다.udlr: 현재 칸에 먼지가 없다면 상하좌우로 1칸 움직입니다.F: 현재 칸에 먼지가 있으면 먼지가 없는 상태로, 먼지가 없으면 먼지가 있는 상태로 만듭니다.
800개 이하의 명령을 사용하여, 격자의 각 칸이 최초에 어떤 상태이든 상관없이 청소기가 있는 칸을 제외하고 모든 칸에 먼지가 없도록 하는 방법을 찾아 제출하세요.
문제 풀이
스포일러 1
먼저, 한 줄의 먼지를 최대한 제거하는 방법을 생각합니다. 칸 수가 256칸인데 주어진 명령의 개수가 800개밖에 되지 않으므로, 대략 1칸당 3개의 명령만을 써야 함을 추측할 수 있습니다.
이를 달성하는 구체적인 방법은, 가로 길이가 일 때, rFr을 번 반복하면 맨 마지막 칸을 제외한 칸의 먼지를 제거하고 맨 오른쪽 칸에 도달할 수 있습니다.
이 동작 하나만을 이용하여 모든 칸의 먼지를 제거할 수 있을까요?
스포일러 2
의외로 비교적 간단한 방법이 존재합니다. 맨 마지막에 벽을 한 바퀴 훑는다고 생각하고, 그 전까지는 벽을 제외한 칸들만 지우는 방법을 생각합니다.
앞에서 찾은 한 줄 지우기 연산은 벽에서 끝나야 하지만 벽에서 시작할 필요는 없습니다. 따라서, UDLR을 이용하여 한 칸 안쪽으로 이동한 후 벽에 닿을 때까지 청소하고, 다음 줄의 한 칸 안쪽으로 이동하여 벽에 닿을 때까지 청소하고, …를 반복할 수 있습니다.
이를 구현하면 아슬아슬하게 800개 명령 제한 내에 들어오는 풀이를 얻을 수 있습니다.
Last updated on