C++를 활용한 행렬에서의 단일 방향 이동 찾기

이 문제에서는 두 점 (x1, y1)과 (x2, y2)를 나타내는 네 개의 값 x1, y1, x2, y2가 주어집니다. 우리의 목표는 행렬 위에서 한 점에서 다른 점으로 이동할 때 필요한 단일 방향을 찾는 것입니다.

이동 거리(칸 수)는 몇 칸이든 상관없지만, 방향은 반드시 하나여야 합니다. 즉, 한 번의 직선 이동만으로 목적지에 도달할 수 있어야 합니다. 결과는 "left", "right", "up", "down" 중 하나의 문자열로 반환하고, 어떤 단일 방향으로도 도달할 수 없다면 -1을 반환하여 "불가능(not possible)"함을 나타냅니다.

예제로 문제 이해하기

입력

x1 = 2, y1 = 1, x2 = 5, y2 = 1

출력

Down

위 예제에서 두 점은 같은 열(y좌표)에 있으므로 세로 방향으로만 이동이 가능하고, 시작 행(x1 = 2)보다 목적지 행(x2 = 5)이 더 크므로 이동 방향은 "Down"이 됩니다.

해결 접근 방법

이 문제의 핵심 아이디어는 간단합니다. 시작점에서 목적지까지 단 한 번의 직선 이동으로 도달하려면, 두 좌표 중 적어도 하나는 서로 같아야 합니다. 즉, x1과 x2가 같거나, y1과 y2가 같아야 합니다.

두 조건을 기준으로 다음과 같은 경우의 수로 나눌 수 있습니다.

Case 1: x1 == x2 && y1 > y2 -> 방향 : Left
Case 2: x1 == x2 && y2 > y1 -> 방향 : Right
Case 3: y1 == y2 && x1 > x2 -> 방향 : Up
Case 4: y1 == y2 && x2 > x1 -> 방향 : Down

두 좌표가 모두 다르다면 대각선 방향의 이동이 필요하므로, 단일 방향으로는 도달할 수 없습니다. 이 경우 "Not Possible"(-1)을 반환합니다.

C++ 구현 코드

위 로직을 C++ 코드로 구현하면 다음과 같습니다.

#include <iostream>
using namespace std;

void findSingleMovement(int x1, int y1, int x2, int y2) {
    if (x1 == x2 && y1 < y2)
        cout << "Right";
    else if (x1 == x2 && y1 > y2)
        cout << "Left";
    else if (y1 == y2 && x1 < x2)
        cout << "Down";
    else if (y1 == y2 && x1 > x2)
        cout << "Up";
    else
        cout << "Not Possible";
}

int main() {
    int x1, y1, x2, y2;
    x1 = 2; y1 = 1;
    x2 = 5; y2 = 1;
    cout << "The direction of movement is ";
    findSingleMovement(x1, y1, x2, y2);
    return 0;
}

출력

The direction of movement is Down

복잡도 분석

이 풀이는 단순히 네 개의 조건을 비교하는 것만으로 동작하므로, 시간 복잡도는 O(1)입니다. 추가적인 메모리 사용도 없어 공간 복잡도 역시 O(1)로 매우 효율적입니다.