[LeetCode] 874. Walking Robot Simulation

https://leetcode.com/problems/walking-robot-simulation/

leetcode - Walking Robot Simulation

문제 유형 : 구현, 해시, 이진탐색

문제 난이도 : Medium

 

문제

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot can receive a sequence of these three possible types of commands:

• -2: Turn left 90 degrees.
• -1: Turn right 90 degrees.
• 1 <= k <= 9: Move forward k units, one unit at a time.

Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, then it will instead stay in its current location and move on to the next command.

Return the maximum Euclidean distance that the robot ever gets from the origin squared (i.e. if the distance is 5, return 25).

Note:

• North means +Y direction.
• East means +X direction.
• South means -Y direction.
• West means -X direction.
• There can be obstacle in [0,0].

 

무한한 XY-좌표평면에 있는  로봇이 북쪽을 바라보고 (0, 0)위치에 있다.

로봇은 다음과 같은 명령어를 받아 수행할 수 있다:

• -2: 왼쪽으로 90도 회전
• -1: 오른쪽으로 90도 회전
• 1 <= k <= 9: k칸만큼 앞으로 이동

일부 평면의 위치에는 장애물이 있다.

로봇이 장애물에 직면하면, 남은 이동이 있더라도 그 앞에서 멈추고 다음 명령어로 넘어간다.

원점으로부터의 유클리드거리의 제곱을 반환하시오. int범위안에 들도록 보장됩니다.

 

풀이

우선, 방향에 대한 숫자 코드를 정의한다.

0: 북, 1: 동, 2: 남, 3: 서

그리고, 위치를 초기화한다. 현재위치:{0, 0}, 현재방향코드:0

 

한 칸씩 이동하면서 장애물을 검색하는 것은 비효율적이라 생각해서, 

x축장애물[x축값] = {장애물들의 y축위치}, y축장애물[y축값] = {장애물들의 x축위치}로 저장시켜서 이동할 때 예정된 목적지와 현재 위치 사이에서 이진탐색을 통해서 장애물의 여부와 현재 위치 출발점으로부터 가장 가까운 장애물을 알아낼 수 있다.

obstacles를 읽으면서 위와같은 <int, vector<int>>의 형태의 해시 테이블을 구성하여 정렬시켜놓는다.

 

이제, 그대로 커맨드를 구현하면 된다.

-2를 받으면 왼쪽으로 회전인데, 숫자 코드 정의상, 현재 숫자 코드에 3을 더하고 4를 나눴을 때의 나머지값이 새로운 방향코드이다.

-1은 1을 더하고 4를 나눴을 때의 나머지값이 되겠다.

그게 아니라면, k칸만큼 이동해야한다.

 

 - 현재 숫자코드가 0이면, 북쪽으로 이동해야 하는데, 이때 x축은 고정이 된다. 즉, x축장애물[현재x값]으로 후보 장애물들을 불러온 뒤, lower_bound로 현재 y값에서 큰 것들중에 가장 가까운 장애물을 검색하여, 그 장애물이 목표 y축위치(현재y + k)보다 작거나 같은지 아니면 큰지 있는지 확인한다.

  목표 y축위치보다 앞에 작거나 같다면, 그 장애물에서 걸린다는 뜻이다. 그 장애물의 y축값-1로 새로 업데이트한다. 

  목표 y축위치보다 크다면, 장애물을 만나지 않는다는 뜻으로, 목표 y축위치로 새로 업데이트한다.

 

 - 현재 숫자코드가 1이면, 동쪽으로 이동해야 하는데, 이때 y축은 고정이 된다. 즉, y축장애물[현재y값]으로 후보 장애물들을 불러온 뒤, lower_bound로 현재 x값에서 큰 것들중에 가장 가까운 장애물을 검색하여, 그 장애물이 목표 x축위치(현재x + k)보다 작거나 같은지 아니면 큰지 확인한다.

  목표 x축위치보다 작거나 같다면, 그 장애물에서 걸린다는 뜻이다. 그 장애물의 x축값-1로 새로 업데이트한다. 

  목표 x축위치보다 크다면, 장애물을 만나지 않는다는 뜻으로, 목표 x축위치로 새로 업데이트한다.

 

 - 현재 숫자코드가 2면, 남쪽으로 이동해야 하는데, 이때 x축은 고정이 된다. 즉, x축장애물[현재x값]으로 후보 장애물들을 불러온 뒤, upper_bound로 현재 y값에서 작은 것들중에 가장 가까운 장애물을 검색하여, 그 장애물이 목표 y축위치(현재y - k)보다 크거나 같은지 아니면 작은지 확인한다.

  목표 y축위치보다 크거나 같다면, 그 장애물에서 걸린다는 뜻이다. 그 장애물의 y축값+1로 새로 업데이트한다. 

  목표 y축위치보다 작다면, 장애물을 만나지 않는다는 뜻으로, 목표 y축위치로 새로 업데이트한다.

 

 - 현재 숫자코드가 3이면, 서쪽으로 이동해야 하는데, 이때 y축은 고정이 된다. 즉, y축장애물[현재y값]으로 후보 장애물들을 불러온 뒤, upper_bound로 현재 x값에서 작은 것들중에 가장 가까운 장애물을 검색하여, 그 장애물이 목표 x축위치(현재x - k)보다 크거나 같은지 아니면 작은지 확인한다.

  목표 x축위치보다 크거나 같다면, 그 장애물에서 걸린다는 뜻이다. 그 장애물의 x축값-1로 새로 업데이트한다. 

  목표 x축위치보다 작다면, 장애물을 만나지 않는다는 뜻으로, 목표 x축위치로 새로 업데이트한다.

 

이러한 움직임을 수행하고, 최대 거리를 업데이트한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        // 0:n, 1:e, 2:s, 3:w
        pair<int, int> pos = {0, 0};
        int dircode = 0;
        int ans = 0;

        unordered_map<int, vector<int>> xAxisObs;
        unordered_map<int, vector<int>> yAxisObs;

        for (const auto &obstacle : obstacles) {
            int x = obstacle[0];
            int y = obstacle[1];
            xAxisObs[x].push_back(y);
            yAxisObs[y].push_back(x);
        }

        for (auto &element : xAxisObs) {
            sort(element.second.begin(), element.second.end());
        }
        for (auto &element : yAxisObs) {
            sort(element.second.begin(), element.second.end());
        }

        for (int command : commands) {
            if (command == -2) {
                dircode = (dircode + 3) % 4;
            } else if (command == -1) {
                dircode = (dircode + 1) % 4;
            } else {
                int k = command;
                int xPos = pos.first;
                int yPos = pos.second;

                if (dircode == 0) {
                    int yGoal = yPos + k;
                    auto it = lower_bound(xAxisObs[xPos].begin(), xAxisObs[xPos].end(), yPos + 1);
                    if (it != xAxisObs[xPos].end() && *it <= yGoal) {
                        yPos = *it - 1;
                    } else {
                        yPos = yGoal;
                    }
                } else if (dircode == 1) {
                    int xGoal = xPos + k;
                    auto it = lower_bound(yAxisObs[yPos].begin(), yAxisObs[yPos].end(), xPos + 1);
                    if (it != yAxisObs[yPos].end() && *it <= xGoal) {
                        xPos = *it - 1;
                    } else {
                        xPos = xGoal;
                    }
                } else if (dircode == 2) {
                    int yGoal = yPos - k;
                    auto it = upper_bound(xAxisObs[xPos].begin(), xAxisObs[xPos].end(), yPos - 1);
                    if (it != xAxisObs[xPos].begin() && *(--it) >= yGoal) {
                        yPos = *it + 1;
                    } else {
                        yPos = yGoal;
                    }
                } else if (dircode == 3) {
                    int xGoal = xPos - k;
                    auto it = upper_bound(yAxisObs[yPos].begin(), yAxisObs[yPos].end(), xPos - 1);
                    if (it != yAxisObs[yPos].begin() && *(--it) >= xGoal) {
                        xPos = *it + 1;
                    } else {
                        xPos = xGoal;
                    }
                }

                pos.first = xPos;
                pos.second = yPos;
                ans = max(ans, pos.first * pos.first + pos.second * pos.second);
            }
        }

        return ans;
    }
};