n × m 크기의 그리드와 시작 지점(x, y)을 나타내는 두 변수 n과 m이 주어집니다.
또한 그리드 내부를 탐색할 때 사용할 수 있는 이동(move) 쌍, 예를 들어 (1,1), (2,2) 같은 형태가 주어집니다. 각 이동 쌍은 x축과 y축으로 이동하는 단위 걸음 수를 의미합니다. 목표는 경계 [1, n] × [1, m] 범위 안에서 그리드 내부를 이동하며 취할 수 있는 총 걸음 수를 구하는 것입니다. 예를 들어 n이 5, m이 4이고 현재 위치가 (2, 2)일 때 선택한 이동이 (1, -1)이라면, 이 이동을 한 번 적용하면 (3, 1)에 도달하지만, 다시 한 번 적용하면 (4, -1)이 되어 y좌표가 -1로 범위를 벗어나므로 유효하지 않습니다.
예제로 이해하기
입력 − A = 3, B = 4, x = 1, y = 1, moves = { {1, 1}, {0, -1} }
출력 − 그리드에서 주어진 방향으로 가능한 이동 횟수 − 4
설명 −
이동 {1,1} 선택 → (2,2) → (3,3) : 2걸음
이동 {0,-1} 선택 → (3,2) → (3,1) : 2걸음
총 4걸음
입력 − A = 4, B = 4, x = 2, y = 2, moves = { {2, 1}, {-2, -3} }
출력 − 그리드에서 주어진 방향으로 가능한 이동 횟수 − 1
설명 −
이동 {2,1} 선택 → (4,3) : 1걸음
이동 {-2,-3} 선택 → (2,0) X 경계를 벗어나므로 불가
총 1걸음
프로그램에서 사용된 접근 방식
이 접근 방식에서는 이동 정보를 pair<int,int> 형태의 벡터로 표현합니다. (x, y) 지점부터 탐색을 시작하고, 벡터에서 하나의 이동을 선택한 뒤 두 방향(x축과 y축)에서 취할 수 있는 이동 횟수 중 최솟값을 고릅니다. 최솟값을 선택해야 경계를 벗어나지 않으면서 최대한 많이 이동할 수 있습니다. 특정 방향으로 이동할 때 현재 위치 x(또는 y)가 n(또는 m)보다 작다면 n(또는 m)에 도달하기까지의 이동 횟수는 (n − 현재 위치) / x입니다. 반대로 1 쪽으로 이동해야 한다면 1에 도달하기까지의 이동 횟수는 (현재 위치 − 1) / |x|입니다.
- A×B 그리드를 나타내는 변수 A, B와 시작점을 나타내는 x, y를 선언합니다.
- 정수 쌍을 담는 벡터(vector<pair<int, int>>)로 이동들을 저장합니다.
- possible_moves(int x, int y, int A, int B, vector<pair<int, int>> move, int size) 함수는 모든 변수와 이동 정보를 받아 그리드에서 주어진 방향으로 가능한 이동 횟수를 반환합니다.
- possible(int x, int temp_x, int A) 함수는 현재 좌표 위치 x, 해당 이동의 좌표 변화량 temp_x, 그 좌표의 그리드 한계 A를 매개변수로 받습니다.
- temp_x가 0이면 INT_MAX를 반환하여 결과값이 최대가 되도록 만듭니다.
- temp_x가 0보다 크면 A에 도달하기 위한 이동 횟수는 |A − x| / temp_x입니다.
- 그렇지 않고 음수라면 1 방향으로 이동하는 횟수는 |x − 1| / temp_x입니다.
- 계산된 이동 횟수를 반환합니다.
- possible_moves() 함수 내부에서 초기 count 값을 0으로 설정합니다.
- for 루프를 사용해 i = 0부터 i < size까지 벡터를 순회합니다.
- 현재 이동 쌍에서 좌표를 추출합니다. 즉 temp_x = move[i].first, temp_y = move[i].second입니다.
- possible() 함수를 이용해 두 방향에서 가능한 이동 횟수 중 최솟값을 check 변수에 저장합니다.
- check의 값을 count에 더하여 총 걸음 수를 누적합니다.
- check를 선택했으므로 x와 y를 check만큼 갱신합니다.
- 마지막으로 그리드에서 주어진 방향으로 가능한 총 이동 횟수를 얻게 됩니다.
- count를 결과로 반환합니다.
이 알고리즘은 각 이동마다 상수 시간의 계산만 수행하므로, 이동 벡터의 크기를 k라고 할 때 시간 복잡도는 O(k)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int possible(int x, int temp_x, int A){
if(temp_x == 0){
return INT_MAX;
}
if (temp_x > 0){
return abs((A - x) / temp_x);
}
else{
return abs((x - 1) / temp_x);
}
}
int possible_moves(int x, int y, int A, int B, vector<pair<int, int>> move, int size){
int count = 0;
for (int i = 0; i < size; i++){
int temp_x = move[i].first;
int temp_y = move[i].second;
int check = min(possible(x, temp_x, A), possible(y, temp_y, B));
count = count + check;
x = x + check * temp_x;
y = y + check * temp_y;
}
return count;
}
int main(){
int A = 3, B = 6, x = 3, y = 3;
vector<pair<int, int> > move = {
{ 2, -1 },
{ 0, 1 },
{ 1, -2 }
};
int size = move.size();
cout<<"Count of possible moves in the given direction in a grid are: "<<possible_moves(x, y, A, B, move, size);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of possible moves in the given direction in a grid are: 3
결과 분석
시작점이 (3, 3)이고 그리드 크기가 3 × 6이므로 각 이동은 다음과 같이 처리됩니다.
- 이동 {2, -1}: x좌표가 이미 최대값인 3이므로 x축 방향으로 더 이상 이동할 수 없어 0걸음입니다.
- 이동 {0, 1}: y좌표가 6에 도달할 때까지 (6 − 3) / 1 = 3걸음 이동할 수 있으며, 위치는 (3, 6)이 됩니다.
- 이동 {1, -2}: x좌표가 이미 3이므로 역시 0걸음입니다.
따라서 그리드 경계 내에서 취할 수 있는 총 이동 횟수는 3이 됩니다.