DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

짐비의 미니언 타기

問題に戻る

解説

시작 위치, 목표 위치, 각 미니언의 위치를 정점으로 보고, 서로의 거리가 RRR 이하인 두 정점을 간선으로 연결한다. 모든 돌진의 비용이 111이므로 정답은 이 그래프에서 시작 정점부터 목표 정점까지의 최단 거리이다.

최단 경로는 같은 정점을 두 번 방문하지 않는다. 따라서 경로 위의 미니언을 차례대로 처치할 수 있으며, 미니언이 사라진다는 규칙 때문에 처치한 미니언의 집합을 별도 상태로 관리할 필요는 없다.

모든 정점 쌍을 확인하면 O(N2)O(N^2)O(N2) 시간이 걸린다. 대신 현재 좌표가 (x,y)(x,y)(x,y)일 때, 다음 조건을 만족하는 정수 쌍 (dx,dy)(d_x,d_y)(dx​,dy​)를 모두 확인한다.

−R≤dx,dy≤R,0<dx2+dy2≤R2.-R\leq d_x,d_y\leq R,\qquad 0<d_x^2+d_y^2\leq R^2.−R≤dx​,dy​≤

가능한 다음 좌표는 (x+dx,y+dy)(x+d_x,y+d_y)(x+dx​,y+dy​)이다. R≤5R\leq5이므로 이러한 좌표는 최대 개이다.

아직 방문하지 않은 미니언과 목표 허수아비의 좌표를 해시 테이블에 저장하고 BFS를 수행한다. 후보 좌표가 해시 테이블에 있으면 방문 거리를 기록하고 큐에 넣은 뒤 해시 테이블에서 삭제한다. 목표를 처음 발견했을 때의 거리가 정답이며, 큐가 빌 때까지 목표를 발견하지 못하면 −1-1−1을 출력한다.

해시 조회와 삭제의 기대 시간이 O(1)O(1)O(1)일 때 전체 기대 시간 복잡도는 O((N+1)R2)O((N+1)R^2)O((N+1)R2)이며, 주어진 사거리 제한에서는 기대 O(N+1)O(N+1)O(N이다. 공간 복잡도는 이다.

좌표의 범위가 −500-500−500 이상 500500500 이하이므로, 두 좌표에 각각 500500500을 더한 뒤 1001×10011001\times10011001×1001 배열에 위치를 저장해도 된다. 배열을 초기화하는 시간을 포함하면 시간 복잡도는 O(10012+(N+1)R2)O(1001^2+(N+1)R^2)O이며, 공간 복잡도는 이다. 범위 밖의 후보 좌표에 접근하지 않도록 주의한다.

Solution written by GPT6

R
,
0
<
dx2​+
dy2​≤
R2.
R≤
5
808080
+
1)
O(N+R2+1)O(N+R^2+1)O(N+R2+1)
(
100
12
+
(N+
1)R2)
O(10012+N+R2)O(1001^2+N+R^2)O(10012+N+R2)