문제 개요
h × w 크기의 격자가 주어지고, 각 칸에는 서로 다른 양의 정수가 하나씩 적혀 있다고 가정해 봅시다. 경로 탐색 로봇이 특정 칸 (p, q)에 놓여 있으며(p는 행 번호, q는 열 번호), 이 로봇을 칸 (i, j)로 이동시킬 수 있습니다. 한 번의 이동에 드는 비용은 |p − i| + |q − j|로 정의됩니다.
이제 다음과 같은 조건을 만족하는 q개의 여행(trip)이 주어집니다.
- 각 여행은 두 값 (x, y)를 가지며, 모든 여행에 공통으로 적용되는 값 d가 존재합니다.
- 로봇은 값이 x인 칸에서 출발하여 값이 x + d인 칸으로 이동합니다.
- 그다음에는 값이 x + 2d인 칸으로 이동하며, 로봇이 y보다 크거나 같은 값을 가진 칸에 도달할 때까지 이 과정을 반복합니다.
- y − x는 항상 d의 배수입니다.
각 여행에 대해 로봇의 총 이동 비용을 구해야 하며, 로봇이 한 번도 이동하지 못하는 경우 해당 여행의 비용은 0입니다.
예제로 이해하기
h = 3, w = 3, d = 3, q = 1이고, 격자와 여행 정보가 다음과 같다고 합시다.
grid = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}
trips = {{3, 9}}
이때 기대하는 출력은 4입니다. 각 값의 위치를 살펴보면 다음과 같습니다.
- 값 3은 칸 (2, 2)에 위치합니다.
- 값 6은 칸 (1, 2)에 위치합니다.
- 값 9는 칸 (3, 3)에 위치합니다.
(2, 2) → (1, 2) 이동 비용은 |2 − 1| + |2 − 2| = 1이고, (1, 2) → (3, 3) 이동 비용은 |1 − 3| + |2 − 3| = 3입니다. 따라서 총 비용은 1 + 3 = 4가 됩니다.
풀이 접근 방법
쿼리마다 로봇의 이동을 직접 시뮬레이션하면 매우 비효율적입니다. 대신 전처리를 통해 각 시작 값 클래스별 이동 비용의 누적합을 미리 계산해 두면, 모든 쿼리를 상수 시간에 처리할 수 있습니다. 구체적인 절차는 다음과 같습니다.
- 맵 loc을 선언하고, 격자의 모든 칸을 순회하면서 각 값이 위치한 좌표 (i, j)를 저장합니다.
- 크기가 d + 1인 dp 배열을 준비합니다. dp[r]은 값이 r로 시작하는 수열(r, r + d, r + 2d, …)에서 인접한 두 값 사이의 이동 비용을 순서대로 담습니다.
- 각 r(1 ≤ r ≤ d)에 대해 인접 이동 비용을 모두 구한 뒤, 이를 누적합(prefix sum) 형태로 변환합니다.
- 각 쿼리 (le, ri)에 대해 ri mod d로 시작 클래스 f를 결정하고, 누적합의 차이를 이용해 구간 [le, ri]의 총 비용을 즉시 계산해 출력합니다.
의사 코드
맵 loc을 하나 정의한다
i := 0부터 i < h까지 1씩 증가시키며 반복:
j := 0부터 j < w까지 1씩 증가시키며 반복:
loc[grid[i, j]] := 새로운 쌍 (i, j)
배열 dp[d + 1]을 정의한다
i := 1부터 i <= d까지 1씩 증가시키며 반복:
j := i
j < w * h인 동안 반복:
n := j + d
만약 j + d > w * h라면:
반복문을 빠져나간다
dx := |loc[n]의 행 값 − loc[j]의 행 값|
dy := |loc[n]의 열 값 − loc[j]의 열 값|
j := j + d
dp[i]의 끝에 dx + dy를 추가한다
j := 1부터 j < dp[i]의 크기까지 1씩 증가시키며 반복:
dp[i, j] := dp[i, j] + dp[i, j − 1]
i := 0부터 i < q까지 1씩 증가시키며 반복:
tot := 0
le := trips[i]의 첫 번째 값
ri := trips[i]의 두 번째 값
만약 ri mod d가 0이라면:
f := d
그렇지 않으면:
f := ri mod d
pxl := (le − f) / d
pxr := (ri − f) / d
만약 le가 f와 같다면:
만약 ri도 f와 같다면:
tot := 0
그렇지 않으면:
tot := tot + dp[f, pxr − 1]
그렇지 않으면:
만약 ri가 f와 같다면:
tot := 0
그렇지 않으면:
tot := tot + dp[f, pxr − 1] − dp[f, pxl − 1]
tot을 출력한다
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 봅시다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
void solve(int h, int w, int d, int q, vector<vector<int>> grid,
vector<pair<int, int>> trips) {
map<int, pair<int, int>> loc;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
loc[grid[i][j]] = make_pair(i, j);
}
vector<int> dp[d + 1];
for (int i = 1; i <= d; i++) {
int j = i;
while (j < w * h) {
int n = j + d;
if (j + d > w * h)
break;
int dx = abs(loc[n].first - loc[j].first);
int dy = abs(loc[n].second - loc[j].second);
j += d;
dp[i].push_back(dx + dy);
}
for (j = 1; j < dp[i].size(); j++)
dp[i][j] += dp[i][j - 1];
}
for (int i = 0; i < q; i++) {
int tot = 0;
int le, ri;
le = trips[i].first;
ri = trips[i].second;
int f;
if (ri % d == 0)
f = d;
else
f = ri % d;
int pxl, pxr;
pxl = (le - f) / d;
pxr = (ri - f) / d;
if (le == f){
if (ri == f)
tot = 0;
else
tot += (dp[f][pxr - 1] - 0);
} else {
if (ri == f)
tot = 0;
else
tot += dp[f][pxr - 1] - dp[f][pxl - 1];
}
cout<< tot << endl;
}
}
int main() {
int h = 3, w = 3, d = 3, q = 1;
vector<vector<int>> grid = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}};
vector<pair<int, int>> trips = {{3, 9}};
solve(h, w, d, q, grid, trips);
return 0;
}
입력
3, 3, 3, 1, {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}, {{3, 9}}
출력
4
복잡도 분석
전처리 단계에서는 각 값의 좌표를 맵에 저장하는 데 O(h × w)의 시간이 걸리고, 인접 이동 비용을 계산하는 과정 역시 전체 수열 길이의 합만큼, 즉 O(h × w)의 시간이 소요됩니다. 이후 각 쿼리는 누적합의 차이만으로 O(1)에 처리되므로, 쿼리 개수가 많아지더라도 효율적으로 동작합니다.