온실 급수 로봇

문제

스마트 온실의 바닥은 R x C 격자로 나뉘어 있습니다. grid[r][c]가 0이면 로봇이 지나갈 수 있는 흙 칸이고, 1이면 화분 선반이 놓여 통과할 수 없는 칸입니다.

급수 로봇은 칸 (sr, sc)에서 방향 dir을 바라본 상태로 켜집니다. 방향은 0=북(행 감소), 1=동(열 증가), 2=남(행 증가), 3=서(열 감소)입니다. 로봇은 켜진 순간 자기가 서 있는 칸에 물을 줍니다.

명령 문자열 commands는 다음 세 가지로만 구성됩니다.

• L — 제자리에서 반시계 방향으로 90도 회전
• R — 제자리에서 시계 방향으로 90도 회전
• F — 바로 뒤에 한 자리 숫자 d(1~9)가 붙어 있고, 바라보는 방향으로 d칸 전진

전진은 한 칸씩 이루어지고, 로봇이 새로 밟는 칸마다 물을 줍니다. 전진 중 다음 칸이 격자 바깥이거나 선반이면 그 칸으로는 들어가지 못하고 충돌 이 일어나며, 이때 로봇은 다음 순서로 반응합니다.

1. 그 F 명령의 남은 전진 칸수를 모두 버린다 (현재 칸에 그대로 머문다).
2. 시계 방향으로 90도 회전한다.
3. 충돌 누적 횟수가 3회 가 되면 배터리 보호 모드로 들어가 남은 명령을 전부 무시하고 즉시 멈춘다.

명령을 모두 수행했거나 배터리 보호 모드로 멈춘 뒤, [물을 준 서로 다른 칸의 수, 최종 행, 최종 열, 최종 방향]을 담은 길이 4의 배열을 반환하는 solution(grid, sr, sc, dir, commands) 함수를 작성하세요. 같은 칸을 여러 번 지나가도 물 준 칸 수는 한 번만 셉니다.

예시

grid=[[0,0,0],[0,0,0],[0,0,0]], sr=2, sc=0, dir=0, commands="F2RF2" → [5,0,2,1]
  (2,0)에서 급수 시작 → 북으로 2칸: (1,0),(0,0) 급수 → R로 동쪽 전환
  → 동으로 2칸: (0,1),(0,2) 급수 → 총 5칸, 최종 (0,2), 방향 1(동)
 
grid=[[0,0,0],[0,0,0],[0,0,0]], sr=1, sc=1, dir=0, commands="F5" → [2,0,1,1]
  (1,1) 급수 → 북으로 1칸 (0,1) 급수 → 다음 칸이 격자 밖이라 충돌 1회
  → 남은 3칸을 버리고 시계 회전하여 동쪽(1)을 바라본 채 종료
 
grid=[[0,0,0,0],[0,1,1,0],[0,0,0,0]], sr=0, sc=0, dir=2, commands="F2RF3RF2" → [5,2,2,1]
  남으로 (1,0),(2,0) 급수 → R로 서쪽 → 왼쪽이 격자 밖이라 충돌 1회, 회전하여 북쪽
  → R로 동쪽 → (2,1),(2,2) 급수 → 총 5칸, 최종 (2,2), 방향 1(동)

제약 조건

• 1 ≤ grid.length(R), grid[0].length(C) ≤ 300
• grid[r][c]는 0 또는 1이고, 시작 칸 grid[sr][sc]는 항상 0입니다.
• 0 ≤ sr < R, 0 ≤ sc < C, dir은 0~3
• commands는 L, R, F와 숫자로만 이루어진 길이 0 이상 3,000 이하의 문자열이며, F 뒤에는 항상 1~9 중 한 글자가 붙어 있습니다.
• 반환값은 길이 4의 정수 배열입니다.

시간 복잡도 목표: O(len(commands) × 9 + R × C)