489. Robot Room Cleaner (Backtracking, Interactive)

링크 - https://leetcode.com/problems/robot-room-cleaner/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

이 문제는 Backtracking을 통해 풀 수 있다. 알고리즘은 다음과 같다.

1. 주어진 방향으로 청소를 하면서 visited에 현재 좌표를 등록하고 나아간다.

2. obstacle이 있거나 방문을 한 좌표때문에 앞으로 나아가지 못한다면, turn right한다.

3. 1,2번을 반복하면서 탐색한다. 그러다가 결국에는 turn right4번을 해도 나아가지 못하는 상황이 발생할 것이다. 그때 go_back을 통해 이전 좌표로 물러난다. 그리고 다시 1,2번을 반복한다.

Code

# """
# This is the robot's control interface.
# You should not implement it, or speculate about its implementation
# """
#class Robot:
#    def move(self):
#        """
#        Returns true if the cell in front is open and robot moves into the cell.
#        Returns false if the cell in front is blocked and robot stays in the current cell.
#        :rtype bool
#        """
#
#    def turnLeft(self):
#        """
#        Robot will stay in the same cell after calling turnLeft/turnRight.
#        Each turn will be 90 degrees.
#        :rtype void
#        """
#
#    def turnRight(self):
#        """
#        Robot will stay in the same cell after calling turnLeft/turnRight.
#        Each turn will be 90 degrees.
#        :rtype void
#        """
#
#    def clean(self):
#        """
#        Clean the current cell.
#        :rtype void
#        """

class Solution:
    def cleanRoom(self, robot):
        """
        :type robot: Robot
        :rtype: None
        """
        visited = set()
        # going clockwise: 0-up, 1-right, 2-down, 3-left
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        def go_back():
            robot.turnRight()
            robot.turnRight()
            robot.move()
            robot.turnRight()
            robot.turnRight()

        def backtrack(cell = (0, 0), d = 0):
            visited.add(cell)
            robot.clean()
            for i in range(4):
                new_d = (d + i) % 4
                new_cell = (cell[0] + directions[new_d][0], cell[1] + directions[new_d][1])
                if not new_cell in visited and robot.move():
                    backtrack(new_cell, new_d)
                    go_back()
                robot.turnRight()

        backtrack()

Complexity

Time Complexity: O(n - m) 여기서 n은 cell의 개수이고, m은 obstacle의 개수이다. 우리는 모든 좌표들을 방문하므로 n-m개의 탐색이 필요하다. 또한 매 좌표마다 4방향으로 확인을 하므로, 총 소요는 4(n-m)이다.

Space Complexity: O(n - m) 우리는 set을 통해 방문한 좌표들을 기록한다.