문제 개요
무한히 넓은 평면 위에 로봇이 하나 있다고 가정해 보겠습니다. 로봇은 처음에 좌표 (0, 0)에 서 있으며 북쪽 방향을 바라보고 있습니다. 로봇은 다음 세 가지 명령 중 하나를 받을 수 있습니다.
- G – 직진하여 1단위 앞으로 이동
- L – 왼쪽으로 90도 회전
- R – 오른쪽으로 90도 회전
로봇은 주어진 명령을 순서대로 수행하며, 이 명령 시퀀스는 끝없이 반복됩니다. 우리가 확인해야 할 것은 로봇이 절대로 벗어나지 않는 원이 평면 위에 존재하는지, 즉 로봇의 이동 경로가 유계(bounded)인지 판별하는 것입니다.
예를 들어 입력이 [GGLLGG]라면 정답은 true입니다. 로봇은 (0, 0)에서 출발해 (0, 2)까지 이동한 뒤 다시 출발점으로 돌아오고, 이후 같은 경로를 무한히 반복하는 닫힌 경로(closed path)를 그리기 때문입니다.
해결 접근 방식
이 문제의 핵심은 명령을 한 번 전부 수행한 뒤 로봇의 최종 상태를 살펴보는 것입니다. 다음 단계를 따릅니다.
- 방향 배열
dir = [[0,1], [1,0], [0,-1], [-1,0]]을 준비합니다. - 현재 위치를 나타낼 pair 변수
temp를 (0, 0)으로, 방향 인덱스k를 0으로 초기화합니다. - 명령 문자열 s를 처음부터 끝까지 순회합니다.
- s[i]가 'G'이면 현재 방향(dir[k])에 따라 temp의 좌표를 이동시킵니다.
- s[i]가 'L'이면 k를 (k + 1) % 4로 갱신하고, 'R'이면 k를 (k - 1 + 4) % 4로 갱신합니다.
- 순회가 끝난 후, 로봇이 원점 (0, 0)에 있거나 방향 인덱스 k가 0이 아니라면 true를, 그렇지 않으면 false를 반환합니다.
핵심 원리
왜 이 조건이 성립할까요?
- 원점으로 돌아온 경우: 명령을 반복해도 항상 같은 닫힌 경로를 그리므로 로봇은 원 안에 갇힙니다.
- 방향이 바뀐 경우(북쪽이 아닌 경우): 사이클을 거듭하면 최대 4번 안에 반드시 원점으로 되돌아오게 됩니다.
- 북쪽을 향한 채 원점이 아닌 경우: 매 사이클마다 같은 방향으로 계속 이동하므로 무한히 멀어집니다. 이 경우에만 false가 됩니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
public:
bool isRobotBounded(string s) {
pair <int, int> temp({0,0});
int k = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == 'G'){
temp.first += dir[k][0];
temp.second += dir[k][1];
}else if(s[i] == 'L'){
k = (k + 1) % 4;
}else{
k = ((k - 1) + 4) % 4;
}
}
return temp.first == 0 && temp.second == 0 || k > 0;
}
};
main(){
Solution ob;
cout << (ob.isRobotBounded("GGLLGG"));
}
입력
"GGLLGG"
출력
1
이처럼 방향 배열과 위치 추적만으로 명령 반복 후 로봇의 상태를 검사하면, 별도의 시뮬레이션 없이도 O(n) 시간 복잡도로 로봇이 원 안에 갇히는지 효율적으로 판별할 수 있습니다.