문제 개요
m × n 크기의 격자(grid)가 주어져 있다고 가정해 보겠습니다. 객체는 셀 (ix, iy)에 놓여 있으며, 우리는 시작 위치 (sx, sy)에서 스캔을 시작해 이 객체를 찾아야 합니다. 스캔 알고리즘은 격자의 셀 (i, j)에 위치할 때마다 i번째 행과 j번째 열을 한 번에 스캔합니다. 객체를 발견하면 스캔이 즉시 중단되고, 발견하지 못하면 스캔 포인터는 (i + 1, j + 1) 위치의 셀로 이동한 뒤 같은 방식으로 다시 스캔을 진행합니다. 이 과정은 객체를 찾을 때까지 반복됩니다. 주어진 위치 정보를 바탕으로, 객체를 찾기 위해 알고리즘이 수행해야 하는 스캔 횟수를 구하는 것이 이 문제의 목표입니다.
예를 들어 입력이 n = 20, m = 20, sx = 3, sy = 2, ix = 12, iy = 4라면, 출력 결과는 2가 됩니다.
풀이 접근 방식
스캔 포인터는 매 단계마다 대각선 방향으로 한 칸씩 이동합니다. 따라서 행 방향(x축)으로 객체에 도달하는 데 필요한 이동 횟수와 열 방향(y축)으로 도달하는 데 필요한 이동 횟수를 각각 계산한 뒤, 둘 중 더 작은 값을 선택하면 그것이 곧 최소 스캔 횟수가 됩니다. 이 문제는 다음 단계를 통해 해결할 수 있습니다.
t1 := (sx <= ix 이면 ix - sx, 아니면 2 * n - ix - sx)
t2 := (sy <= iy 이면 iy - sy, 아니면 2 * m - iy - sy)
(t1, t2) 중 최솟값 출력
여기서 t1은 행 기준으로 객체까지 걸리는 스캔 횟수, t2는 열 기준으로 객체까지 걸리는 스캔 횟수를 의미합니다. 시작 지점이 객체보다 뒤에 있는 경우에는 격자 전체 크기를 활용해 순환적으로 거리를 계산합니다.
구현 예시
다음 C++ 구현 예시를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, int m, int sx, int sy, int ix, int iy) {
int t1 = (sx <= ix ? ix - sx : 2 * n - ix - sx);
int t2 = (sy <= iy ? iy - sy : 2 * m - iy - sy);
cout << min(t1, t2);
}
int main() {
int n = 20, m = 20, sx = 3, sy = 2, ix = 12, iy = 4;
solve(n, m, sx, sy, ix, iy);
return 0;
}
입력
20, 20, 3, 2, 12, 4
출력
2
마무리
이 알고리즘은 별도의 시뮬레이션 없이 두 개의 산술 연산만으로 정답을 구하므로, 시간 복잡도는 O(1)로 매우 효율적입니다. 격자 문제에서 대각선 이동과 순환 거리 계산의 원리를 이해하는 데 좋은 예제가 됩니다.