[BOJ 24680] Silver-16

문제 링크

일단 하나의 line을 잡아서 해당 라인의 맨 끝 칸을 제외하고 청소를 하는 방법들을 고민해볼 수 있다. 만일 line의 맨 왼쪽에서 시작하여 하나의 가로줄을 청소해본다고 하자. 처음 생각했던 방법은 rFrFrF…를 반복하는 것이다. 해당 방법은 칸당 \(4\)개 이상의 쿼리를 필요로 하므로 문제를 해결할 수 없는 방법이다. 최악의 케이스:(OXXXX…XXX; O는 먼지가 있는 칸, X는 먼지가 없는 칸)
위 전략에서 문제가 되는 부분은 \(i\)번째 칸을 지우고 \(i+1\)번째 칸으로 이동했을 때 해당 칸이 X라면 그 칸을 O로 토글하면서 매우 비효율적인 행동이 일어난다는 것인데, 모든 쿼리를 rrF로 바꿔준다면 \(i+1\)번째 칸이 X인경우 바로 \(i+2\)번째 칸으로 이동할 수 있고, O인 경우 \(i+1\)번째 칸에 위치한 상태로 해당 칸을 X로 바꿀 수 있다. 즉, 3번의 쿼리로 한 칸 이상을 무조건 X로 만들 수 있다. 또한, 잘 생각해보면 첫 rrF는 rF만 해도 된다.
그럼 이제 하나의 line을 해결하는 방법을 알아냈으니, 여러개의 line을 효율적으로 해결하는 방법들을 생각해보아야 한다. 여기서 여러가지 애로사항이 발생한다.
먼저 모든 가로줄을 좌→우로 슬라이딩 하는 전략을 떠올려볼 수 있다. 근데 이렇게 하려면 칸당 평균 \(3\)회의 쿼리를 통해 하나의 line을 청소한 뒤, 다음 line의 가장 왼쪽 칸으로 이동하기 위해서 칸당 \(1\)회의 쿼리를 더 사용해서 이동해야 하므로 벌써부터 역부족인걸 알 수 있다.
그럼 이제 각 line을 지그재그로 처리해야 한다는 사실을 알게되는데, 여기서 또 문제가 되는것은 첫 세로줄과 마지막 세로줄의 상태를 알 수 없으므로 서로 동떨어진 위치의 2개의 세로줄을 청소해줘야 한다는 사실이다.
각 line을 처리하는데 걸리는 쿼리 횟수를 계산해보자. 15개의 칸에 대해서 rFrrFrrF…r or lFllFllF…l을 사용한 뒤 D를 사용해야 하므로 하나의 가로줄당 \(45\)개의 쿼리를 사용하게 되고, 남은 80개의 쿼리로 2개의 세로줄을 처리하기엔 역부족으로 보인다.
여기서 일단 한 가지 최적화를 해보자. 어차피 양 끝의 세로줄의 정보를 알 수 없다면 매번 15개의 칸을 청소하지 말고 중심에 존재하는 14개의 칸만 청소하는 전략을 생각해볼 수 있다. 여기서 중요한건 처음에 R쿼리를 한번 날린 뒤 rFrrFrrF…rrF를 하면 현재 15번째 칸에 있을지 16번째 칸에 있을지 모르는데, 이건 RLD쿼리를 날려줘서 무조건 15번째 칸으로 옮기고 한칸 아래로 옮길 수 있다. 이렇게 하면 대충 하나의 line당 \(1\)개의 쿼리가 줄어서 15개의 여유 쿼리가 생겼다. \(95\)개정도의 쿼리면 2개의 세로줄을 커버할 수 있지 않을까?
근데 이제 2개의 세로줄이 동떨어져 있기 때문에, 각 세로줄을 \(45\)회의 쿼리로 처리한다고 해도 쓰레기가 있는 칸이 2개가 존재할 수 있으며 이걸 처리하는데 \(30\)회 이상의 쿼리를 필요로 한다.
여기서 마지막 아이디어를 적용할 것이다. 마지막에 결국 첫 번째 세로줄을 처리한 후 마지막 세로줄로 이동하는 경로가 필연적으로 존재하게 된다는 것을 알 수 있다. 그렇다면 가로줄들을 청소할때 가로줄 하나를 남겨놓으면 해당 줄을 청소하면서 자연스럽게 다른 세로줄을 향해 넘어갈 수 있다는 것이다.
결론적으로 전략은 이렇다. 처음에 RD쿼리를 날려서 \((2, 2)\)점에서 시작한다. rFrrF…RLD or lFllF…LRD쿼리를 통해 각 가로줄의 가운데 14칸의 쓰레기를 청소한다. 이후 Π모양의 남은 칸을 스위핑 쭉 해주면 끝난다. 이렇게 풀면 \(795\)회의 쿼리가 필요하고, 정해는 맨 아래 가로줄도 남겨놓은 뒤 마지막에 해당 가로줄을 지워주는데 이렇게 하면 \(2\)회의 쿼리를 더 아껴서 \(793\)회로 조건에 만족하는 청소를 진행할 수 있다.

※ 쿼리를 구성할때 고려하면 좋은 점

F쿼리는 무언가 이동을 시행하기 전에 날리면 무의미한 쿼리가 된다. 해당 위치의 시작 상태를 토글링하면 F쿼리를 날리지 않은 것과 동등한 상태인데 쿼리만 한 번 날리는 것이 되기 때문이다. 이런 점들을 고려하면 문제에서 내가 할 수 있는 행동이 몇개 없어서 금방 최적의 쿼리들을 찾아낼 수 있다.
문제에서 쿼리의 제한이 \(800\)회인데, 청소해야 하는 칸의 수는 \(16\times16=256\)칸이다. 즉 칸마다 평균적으로 거의 3회의 쿼리만 사용해서 처리해야 함을 직관적으로 알아낼 수 있다. 이런 특이한 제한조건은 스페셜 저지 혹은 인터렉티브 문제들에서 주의깊게 보는게 좋은거같다.