문자열 s가 로봇의 이동 명령을 나타낸다고 가정해 보겠습니다. 로봇은 현재 좌표 (0, 0)에 위치하고 있으며 북쪽을 바라보고 있습니다. 이동 문자열 s에는 다음과 같은 문자들이 포함될 수 있습니다.
- "F" : 현재 바라보는 방향으로 한 칸 전진
- "L" : 왼쪽으로 90도 회전
- "R" : 오른쪽으로 90도 회전
로봇이 문자열 s에 담긴 이동을 순서대로 무한히 반복한다고 할 때, 평면 위에 로봇이 절대 벗어날 수 없는 경계 상자(bounding box)가 존재하는지 확인하는 것이 문제입니다.
예를 들어 입력이 s = "FFRFRFFRF"라면 출력은 True가 됩니다. 로봇은 북쪽으로 2칸 이동한 뒤 오른쪽으로 90도 회전하여 1칸 전진하고, 다시 오른쪽으로 90도 회전하여 남쪽으로 2칸 이동한 후 또다시 오른쪽으로 회전하기 때문입니다. 즉, 로봇의 이동 경로가 하나의 사각형을 이루므로 경계 상자가 존재하게 됩니다.
접근 방법
핵심 아이디어는 로봇의 위치와 방향을 시뮬레이션하면서, 이동 사이클을 최대 4번 반복했을 때 원점으로 돌아오는지 확인하는 것입니다. 한 사이클이 끝난 후 로봇이 원점에 있다면, 어떻게 반복하더라도 로봇은 항상 유한한 영역 안에서 움직이게 됩니다. 해결 절차는 다음과 같습니다.
- 방향 배열 moves를 [[0, -1], [1, 0], [0, 1], [-1, 0]]로 초기화합니다. 각각 서쪽, 남쪽, 동쪽, 북쪽을 의미합니다.
- 현재 위치 r, c를 0, 0으로 설정합니다.
- 현재 방향 인덱스 d를 0으로 설정합니다.
- 4번의 사이클 동안 다음을 반복합니다.
- 문자열 s의 각 문자에 대해
- s[i]가 "F"이면 (r, c)를 (r + moves[d][0], c + moves[d][1])로 갱신합니다.
- s[i]가 "L"이면 d를 (d + 3) % 4로 갱신합니다(왼쪽 90도 회전).
- s[i]가 "R"이면 d를 (d + 1) % 4로 갱신합니다(오른쪽 90도 회전).
- 사이클이 끝난 후 r == 0이고 c == 0이면 True를 반환합니다.
- 문자열 s의 각 문자에 대해
- 4번의 사이클 동안 원점으로 돌아오지 않으면 False를 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
def solve(s):
moves = [[0, -1], [1, 0], [0, 1], [-1, 0]]
r, c = 0, 0
d = 0
for times in range(4):
for i in range(len(s)):
if s[i] == "F":
r, c = r + moves[d][0], c + moves[d][1]
elif s[i] == "L":
d = (d + 3) % 4
elif s[i] == "R":
d = (d + 1) % 4
if r == 0 and c == 0:
return True
return False
s = "FFRFRFFRF"
print(solve(s))입력
"FFRFRFFRF"
출력
True
이 알고리즘의 시간 복잡도는 O(n)이며, 여기서 n은 문자열 s의 길이입니다. 사이클을 최대 4번만 반복하면 되기 때문에 전체 연산 횟수는 4n으로 일정한 상수 배수에 머물러 효율적입니다.