[LeedCode] 1041. Robot Bounded In Circle 파이썬 Medium

문제 해석:

명령어가 문자열로 입력된다. 
명령어는 각각, G,  L, R로 주어지는데, 
G : 앞으로가기
L : 왼쪽으로 방향전환
G : 오른쪽으로 방향전환
이렇게 로봇은 명령어에 따라 움직일 수 있다. 
이 명령어를 계속 수행했을때, 로봇이 무한한 서클에 빠지는지 아닌지를 확인해라.

문제 해설:

( 처음에 방향이 4개니까 최대 5번 반복하면 어찌됬던 같은 위치에 도착한다고 생각했다가 실패했다. )

1. 두가지 조건으로 무한 써클에 빠지는지 아닌지 알 수 있다.
2. 처음 명령어를 한번 진행했을때 처음 좌표로 오게 된다면 그것은 무한 써클이다.
3. 처음 명령어를 한번 진행했을때 북쪽을 보고 있지 않는다면 그것은 무한 써클이다.
이에 대한 증명이 있는데, 2번은 사실 명령어를 모두 수행후 초기 위치로 오면 다시 반복이기 때문에 옳다.
3번은, 처음 시작점의 위치가 북쪽이기 때문에, 도중에 어떤 방향을 다녀왔어도 다시 북쪽을 보고 있다면 계속해서 북쪽을 향해 전진한다.
반대로 동, 서, 남쪽을 가르키는경우, 총 4번의 명령어 수행이 끝나고나면 최종적으로 다시 북쪽을 향하고 있는 방향전환이 4번, 4번, 2번일어난다. 이는 로봇이 이동하는 과정에서 (4개의 방향) 마지막에 바뀌는 방향에따라 최종적으로 어떻게 될지 예측할 수 있다. 

1041. Robot Bounded In Circle

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

• "G": go straight 1 unit;
• "L": turn 90 degrees to the left;
• "R": turn 90 degrees to the right.

The robot performs the instructions

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

 

Example 1:

Input: instructions = "GGLLGG" Output: true Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0). When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

Example 2:

Input: instructions = "GG" Output: false Explanation: The robot moves north indefinitely.

Example 3:

Input: instructions = "GL" Output: true Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

 

Constraints:

• 1 <= instructions.length <= 100
• instructions[i] is 'G', 'L' or, 'R'.

소스코드:

4 싸이클 버전

# 첫번째 코드 4방향을 모두 돌고나서, 처음 위치로 오면 무한서클, 아니면 무한서클 아님
class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        # N, R, S, W
        dir = [[-1, 0], [0, 1], [1, 0], [0, -1], ]
        used = []
        now_dir = 0
        ny = 0
        nx = 0
        for j in range(4):
            for i in range(len(instructions)):
                if instructions[i] == "G":
                    ny = ny + dir[now_dir][0]
                    nx = nx + dir[now_dir][1]
                elif instructions[i] == "L":
                    now_dir = 3 if now_dir == 0 else now_dir - 1
                elif instructions[i] == "R":
                    now_dir = (now_dir + 1) % 4
        if ny == 0 and nx == 0 and now_dir == 0: return True
        else: return False

증명을 통한 버전

# 명령어가 한번 끝나고, 처음 좌표 위치거나, 북쪽이 아닐때는 무한 서클
class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        x = y = 0
        idx = 0
        for i in instructions:
            if i == "L":
                idx = (idx + 3) % 4
            elif i == "R":
                idx = (idx + 1) % 4
            else:
                x += dir[idx][0]
                y += dir[idx][1]
        if y == 0 and x == 0:
            return True
        elif idx != 0:
            return True
        else:
            return False