---
id: "imported/blog/history/ex/ahc-27"
title: "AHC 27"
description: "이 글은 AHC 27의 풀이 방법에 대해 내 접근을 정리한 글이다."
kind: "record"
published: "2023-12-10T00:00:00.000Z"
tags: ["PS","atcoder"]
url: "https://www.readiz.com/blog/history/ex/ahc-27/"
markdownUrl: "https://www.readiz.com/blog/history/ex/ahc-27/index.md"
---

# AHC 27

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

# 문제 분석

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

# Score 식 분석

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

# 초반 전략

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

# 중반 전략

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

# 후반 전략

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

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