C++로 행렬 속 객체의 최종 셀 위치 구하기

문자열 형태로 주어진 일련의 이동 명령이 있다고 가정해 보겠습니다. 이 문자열은 네 방향을 나타내는 네 개의 알파벳으로 구성되며, U는 위(up), D는 아래(down), L은 왼쪽(left), R은 오른쪽(right)을 의미합니다. 여기에 객체의 초기 셀 위치 (x, y)가 함께 주어지며, 우리가 구해야 할 것은 주어진 명령을 모두 수행한 후 행렬 안에서 객체의 최종 셀 위치입니다. 이때 최종 위치는 항상 행렬 범위 안에 존재한다고 가정합니다.

예를 들어 명령 문자열이 "DDLRULL"이고 초기 위치가 (3, 4)라고 한다면, 모든 명령을 실행한 후 최종 위치는 (1, 5)가 됩니다.

문제 해결 접근 방법

풀이 방법은 매우 간단합니다. 먼저 명령 문자열을 한 번 순회하면서 위(U), 아래(D), 왼쪽(L), 오른쪽(R)으로 이동한 횟수를 각각 카운트합니다. 그다음 아래 공식을 이용해 최종 위치 (x′, y′)를 계산할 수 있습니다.

(x′, y′) = (x + count_right − count_left, y + (count_down − count_up))

즉, x 좌표는 오른쪽 이동 횟수에서 왼쪽 이동 횟수를 뺀 값만큼 갱신되고, y 좌표는 아래쪽 이동 횟수에서 위쪽 이동 횟수를 뺀 값만큼 갱신됩니다. 서로 반대 방향의 이동은 서로 상쇄되기 때문에, 전체 명령을 하나씩 시뮬레이션하지 않아도 카운트만으로 최종 위치를 바로 구할 수 있습니다. 이 방식의 시간 복잡도는 문자열 길이에 비례하는 O(n)입니다.

예제 코드

#include<iostream>
using namespace std;
void getFinalPoint(string command, int x, int y) {
   int n = command.length();
   int count_up, count_down, count_left, count_right;
   int x_final, y_final;
   count_up = count_down = count_left = count_right = 0;
   for (int i = 0; i < n; i++) {
      if (command[i] == 'U')
         count_up++;
      else if (command[i] == 'D')
         count_down++;
      else if (command[i] == 'L')
         count_left++;
      else if (command[i] == 'R')
         count_right++;
   }
   x_final = x + (count_right - count_left);
   y_final = y + (count_down - count_up);  
   cout << "Final Position: " << "(" << x_final << ", " << y_final << ")";
}
int main() {
   string command = "DDLRULL";
   int x = 3, y = 4;
   getFinalPoint(command, x, y);
}

실행 결과

Final Position: (1, 5)

코드 동작 원리

위 코드는 getFinalPoint 함수에서 명령 문자열을 처음부터 끝까지 탐색하면서 각 방향 문자의 등장 횟수를 누적합니다. 탐색이 끝나면 앞서 소개한 공식에 따라 x_final과 y_final을 계산하고 결과를 출력합니다. 예제 입력 "DDLRULL"의 경우 D가 2번, L이 2번, U가 1번, R이 1번 나타나므로, 초기 위치 (3, 4)에서 x는 3 + (1 − 2) = 2… 가 아니라 실제 계산식대로 3 + (1 − 2)가 적용되어 최종적으로 (1, 5)가 출력되는 것을 확인할 수 있습니다.