C++로 시작 좌표에서 목표 좌표까지 이동 가능 여부 확인하기

문제 개요

두 개의 좌표 (sx, sy)와 (tx, ty)가 주어졌을 때, 시작점 (sx, sy)에서 도착점 (tx, ty)까지 이동할 수 있는지 판별하는 문제입니다.

허용되는 이동은 현재 점 (x, y)에 대해 다음 두 가지 변환 중 하나를 적용하는 것뿐입니다.

(x, y) → (x, x + y)
(x, y) → (x + y, y)

예를 들어, 시작점이 (1, 1)이고 목표점이 (4, 5)라면 답은 true(이동 가능)입니다. 실제 이동 경로는 다음과 같습니다.

(1, 1) → (2, 1)
(2, 1) → (3, 1)
(3, 1) → (4, 1)
(4, 1) → (4, 5)

접근 방식: 역방향 탐색

시작점에서 목표점을 향해 순방향으로 시뮬레이션하면 매 단계마다 두 가지 선택지가 생기므로 경우의 수가 지수적으로 증가하여 비효율적입니다. 따라서 목표점에서 시작점을 향해 거꾸로 거슬러 올라가는 역방향 탐색을 사용하는 것이 효과적입니다.

역방향으로 볼 때 각 단계에서는 더 큰 좌표 값에서 작은 좌표 값을 빼는 연산만 고려하면 됩니다. 같은 값을 여러 번 반복해서 빼는 과정을 나눗셈(모듈로) 연산 하나로 압축하면 유클리드 호제법과 유사한 방식으로 매우 빠르게 처리할 수 있습니다.

알고리즘 단계

tx > sx 이고 ty > sy 인 동안 다음을 반복합니다.
- tx > ty 이면 tx := tx mod ty
- 그렇지 않으면 ty := ty mod tx
반복이 끝난 후 아래 조건 중 하나라도 만족하면 true를 반환합니다.
- sx == tx 이고 sy <= ty 이며 (ty − sy) mod tx == 0
- sy == ty 이고 tx >= sx 이며 (tx − sx) mod ty == 0

이 조건의 의미는 다음과 같습니다. 반복 종료 후 한 좌표가 시작점과 일치하면, 나머지 좌표의 차이가 일치하는 좌표 값으로 정확히 나누어떨어져야만 해당 축 방향으로 원하는 횟수만큼 이동이 가능하기 때문입니다.

C++ 구현 예제

다음 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

bool solve(int sx, int sy, int tx, int ty) {
    while (tx > sx && ty > sy) {
        if (tx > ty) {
            tx %= ty;
        } else {
            ty %= tx;
        }
    }
    return (sx == tx && sy <= ty && (ty - sy) % tx == 0)
        || (sy == ty && tx >= sx && (tx - sx) % ty == 0);
}

int main() {
    cout << solve(1, 1, 4, 5);
}

입력

1, 1, 4, 5

출력

출력값 1은 불린 값 true, 즉 (1, 1)에서 (4, 5)로의 이동이 가능함을 의미합니다.

복잡도 분석

매 반복마다 좌표 값이 최소 절반 이상 감소하므로, 시간 복잡도는 유클리드 호제법과 동일하게 O(log(max(tx, ty)))입니다. 공간 복잡도는 추가 배열 없이 상수 변수만 사용하므로 O(1)입니다.