[LeetCode] 2849. Determine if a Cell Is Reachable at a Given Time

https://leetcode.com/problems/determine-if-a-cell-is-reachable-at-a-given-time/solutions/

Determine if a Cell Is Reachable at a Given Time - LeetCode

leetcode - Determine if a Cell is Reachavle at a Given Time

문제 유형 : 수학

문제 난이도 : Medium

 

문제

You are given four integers sx, sy, fx, fy, and a non-negative integer t.

In an infinite 2D grid, you start at the cell (sx, sy). Each second, you must move to any of its adjacent cells.

Return true if you can reach cell (fx, fy) after exactly t seconds, or false otherwise.

A cell's adjacent cells are the 8 cells around it that share at least one corner with it. You can visit the same cell several times.

 

당신은 양수 sx, sy, fx, fy, t를 받는다.

2차원 평면에서 (sx, sy)부터 시작해서 (fx, fy)까지 가야 한다. 상하좌우대각선으로 한 칸 움직이는데 1초가 걸린다.

정확히 t초만에 도달할 수 있으면 true를, 아니면 false를 반환하라.

당신은 같은 셀을 또 방문할 수 있다.

 

 

풀이

어려워 보이고, dp나 탐색을 사용해야 할 것 같지만, 사실 간단하다.

대각선으로 가는 데 1초가 걸리므로, x좌표간의 차이 또는 y좌표간의 차이 중 둘 중에서 가장 큰 차가 바로 최단 시간에 도착하는 방법이다.

최단 시간이 t초 이내라면, 그 지점에 정확히 t초를 맞춰서 갈 수 있다.(대각선으로 한번 가는걸 상 또는 하 + 좌 또는 우로 가면 1초에 가는 이동을 2초만에 갈 수 있다. 이 방법으로 최단 시간이 t 이하라면 정확히 t초만에 도착하는 경우를 만들 수 있다.)

 

반례하나가 존재한다. 시작점과 끝점이 같고, t가 1인 경우이다. 이 경우에는 정확히 1초만에 도착할 수 없다.

이 경우의 예외처리만 해주면 된다.

 

차가 음수가 될 수 있으므로, 절댓값을 씌워주는 걸 잊지 말자.

 

코드

C++

class Solution {
public:
    bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        if(sx == fx && sy == fy && t == 1) return false;
        return max(abs(sx-fx), abs(sy-fy)) <= t;
    }
};