시작 위치, 목표 위치, 각 미니언의 위치를 정점으로 보고, 서로의 거리가 이하인 두 정점을 간선으로 연결한다. 모든 돌진의 비용이 이므로 정답은 이 그래프에서 시작 정점부터 목표 정점까지의 최단 거리이다.
최단 경로는 같은 정점을 두 번 방문하지 않는다. 따라서 경로 위의 미니언을 차례대로 처치할 수 있으며, 미니언이 사라진다는 규칙 때문에 처치한 미니언의 집합을 별도 상태로 관리할 필요는 없다.
모든 정점 쌍을 확인하면 시간이 걸린다. 대신 현재 좌표가 일 때, 다음 조건을 만족하는 정수 쌍 를 모두 확인한다.
가능한 다음 좌표는 이다. 이므로 이러한 좌표는 최대 개이다.
아직 방문하지 않은 미니언과 목표 허수아비의 좌표를 해시 테이블에 저장하고 BFS를 수행한다. 후보 좌표가 해시 테이블에 있으면 방문 거리를 기록하고 큐에 넣은 뒤 해시 테이블에서 삭제한다. 목표를 처음 발견했을 때의 거리가 정답이며, 큐가 빌 때까지 목표를 발견하지 못하면 을 출력한다.
해시 조회와 삭제의 기대 시간이 일 때 전체 기대 시간 복잡도는 이며, 주어진 사거리 제한에서는 기대 이다. 공간 복잡도는 이다.
좌표의 범위가 이상 이하이므로, 두 좌표에 각각 을 더한 뒤 배열에 위치를 저장해도 된다. 배열을 초기화하는 시간을 포함하면 시간 복잡도는 이며, 공간 복잡도는 이다. 범위 밖의 후보 좌표에 접근하지 않도록 주의한다.
Solution written by GPT6