이 글은 AHC 27의 풀이 방법에 대해 내 접근을 정리한 글이다.

문제 분석

$20 \times 20$ 크기부터 $40 \times 40$ 크기를 가지는 2차원 맵이 있고, 이 맵 위를 로봇 청소기가 지나간다. 원점에서 출발해서 원점으로 돌아오는 경로를 하나 리턴해야하고, 이 경로는 기본적으로 짧을 수록 좋다. 그렇지만, 각 구역마다 장애물이 존재하며, 구역마다 쓰레기가 쌓이는 속도가 다르기 때문에, 경로를 잘 만들어야 한다.

Score 식 분석

일단 길이 $L$의 path를 만들었다고 치면, 한번 로봇을 순회시킨다. 그러고나서, $L$ ~ $2L - 1$ 구간 경로 방문을 시키면서, 전체 맵의 더러움 정도를 합한 것이 스코어가 된다.

초반 전략

dfs 알고리즘을 통해 깊이 우선으로 탐색시켜, 최대한 방문한 곳은 1번만 방문하는 식으로 해서 다시 원점으로 복귀하도록 했다.

중반 전략

dfs 도 여러 방법으로 방문이 가능함에 착안, score를 계산할 수 있도록 로직을 짰고, 여러 dfs 경로 중 score가 최소가 되는 경로를 리턴하도록 했다.

후반 전략

딱히 후반 전략을 떠올리지 못했다. 영역을 나눠야 한다.. 까지는 생각했지만, 영역을 나누고 어떻게 방문하지? 에서 구현을 실제로 이루어내지는 못했음.

다른 후기글을 읽어보니 빔 탐색 등을 활용해서, 역시 쉽게 더러워지는 곳을 여러번 방문하도록 경로를 짜는 방법이 주효. 만약 이렇게 탐색했는데 미방문 지역이 있다면, 끝에 미방문 지역을 붙이는 것이 아니라 기존 경로를 최대한 수정하는 방식으로 미방문 지역을 방문하도록 조작하는듯 하다.