DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

짐비의 미니언 타기

문제로 돌아가기

해설

시작 위치, 목표 위치, 각 미니언의 위치를 정점으로 보고, 서로의 거리가 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)