C++로 풀어보는 로봇 원점 복귀 문제: 이동 경로 판별 알고리즘

로봇이 좌표 평면 위의 시작점 (0, 0)에서 출발한다고 가정해 봅시다. 로봇의 이동 순서가 문자열로 주어졌을 때, 모든 이동을 마친 후 로봇이 다시 원점 (0, 0)으로 돌아오는지 판별하는 것이 이 문제의 목표입니다.

문제 설명

이동 순서는 문자열 형태로 주어지며, 각 문자는 로봇의 i번째 이동을 나타냅니다.

R: 오른쪽으로 한 칸 이동
L: 왼쪽으로 한 칸 이동
U: 위쪽으로 한 칸 이동
D: 아래쪽으로 한 칸 이동

모든 이동이 끝난 후 로봇이 원점에 도달했다면 true를, 그렇지 않다면 false를 반환해야 합니다.

예를 들어 입력이 "RRULLD"라면 결과는 true입니다. 오른쪽으로 두 칸 이동한 뒤, 위로 한 칸, 왼쪽으로 두 칸, 다시 아래로 한 칸 이동하면 결국 시작 위치인 원점으로 되돌아오기 때문입니다.

해결 접근 방법

이 문제는 간단한 카운팅 기법으로 해결할 수 있습니다. 좌우 방향과 상하 방향의 이동 횟수가 서로 상쇄되어 0이 된다면 로봇은 원점에 있는 것입니다.

이동 문자열의 길이를 l에 저장합니다.
길이가 0이라면 이동이 없으므로 즉시 true를 반환합니다.
왼쪽 이동 카운터 lft와 위쪽 이동 카운터 up을 0으로 초기화합니다.
문자열을 순회하며 각 문자에 따라 카운터를 증감합니다.
- 'L'이면 lft를 1 증가, 'R'이면 lft를 1 감소
- 'U'이면 up을 1 증가, 'D'이면 up을 1 감소
순회가 끝난 후 lft와 up이 모두 0이면 true, 아니면 false를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool judgeCircle(string moves) {
        int l = moves.length();
        if (l == 0) {
            return true;
        }
        int lft = 0, up = 0;
        for (int i = 0; i < l; i++) {
            if (moves[i] == 'L') {
                lft++;
            }
            if (moves[i] == 'R') {
                lft--;
            }
            if (moves[i] == 'U') {
                up++;
            }
            if (moves[i] == 'D') {
                up--;
            }
        }
        if (lft == 0 && up == 0) {
            return true;
        }
        return false;
    }
};
main(){
    Solution ob;
    cout << (ob.judgeCircle("RRULLD"));
}

입력

"RRULLD"

출력

복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간은 카운터 두 개만 사용하므로 공간 복잡도는 O(1)입니다.

마무리

로봇 원점 복귀 문제는 좌표 계산 대신 방향별 이동 횟수의 균형만 확인하면 되는 대표적인 문자열 처리 문제입니다. 'R'과 'L'의 개수가 같고, 'U'와 'D'의 개수가 같다면 반드시 원점으로 돌아온다는 핵심 아이디어만 기억하면 됩니다.