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

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

 

문   제 : 

최대로 잡을 수 있는 몬스터의 수를 반환해라.

시작좌표 (sx, sy) , 목표좌표 (fx, fy)가 주어진다. ( 시작좌표와 목표좌표는 1사분면에 있다, )

그리고 시간(턴) t가 주어진다.

시작좌표에서 t번 이동했을 때 목표좌표까지 도달할 수 있는지 아닌지를 반환해라.

단, 이동은 8방향으로 가능하다. (상하좌우 대각선)

단, 같은 좌표를 여러 번 방문해도 된다.

 

Constraint

{ 1 <= sx, sy, fx, fy <= 10^9 }

{ 1 <= t <= 10^9  }

 

 

Matter

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.

 

Example )

Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6
Output: true

Explanation: 
Starting at cell (2, 4), we can reach cell (7, 7) in exactly 6 seconds by going through the cells depicted in the picture above.

=======================================================================================
Example 2:

Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3
Output: false

Explanation: 
Starting at cell (3, 1), it takes at least 4 seconds to reach cell (7, 3) by going through the cells depicted in the picture above. 
Hence, we cannot reach cell (7, 3) at the third second.

---

해    결  &  설    명: 

처음에 이 문제를 봤을 땐 단순한 델타 문제인줄 알고 재귀함수를 이용해 풀려고 했다.

하지만 보통의 델타문제와 다른 2가지 조건이 있었다. 

• 각 셀에 중복방문이 가능하다는 것
• 4방 탐색이 아닌 8방 탐색이라는 것

위 2가지 조건 때문에 재귀로 해결하려고 할 시, 스택오버플로우가 날 것이 뻔했다. (방문처리를 안하고 8방향의 제곱만큼 쌓이기 때문에)

 

따라서 알고리즘 풀이 접근이 아닌 수학적 방법론으로 접근했다.

 

먼저 시작좌표와 목표좌표가 같은 지점인가 아닌가 두 가지 경우로 나눌 수 있다.

 

만약 시작좌표와 목표좌표가 같다면?

t번의 이동으로 시작했던 곳으로 다시 돌아와야 한다는 뜻이다.

즉, t가 1이 아니기만 하면 어떻게든 뱅뱅 돌아서 돌아올수가 있다. 특수한 2가지 조건 때문에 말이다. (중복방문, 대각이동)

 

만약 시작좌표와 목표좌표가 다르다면?

먼저 대각이동을 이해해야한다.

대각이동은 (상하,좌우) 이동을 묶어서 연속으로 한 것이나 다름없다.

즉, 2번갈 것을 1번으로 단축해 가는 방법이다.

 

ㄱ자로 가는 거리를 구한다. -> 대각이동을 하지 않고 가는 경우

만약에 대각이동을 하지 않고 (길 단축 방법을 하지 않고) 갔는데 t가 더 작다면? - 턴이 모자르다는 뜻

이 말은 길을 좀 단축해서 가야 t만에 도달할 수 있다는 뜻이다.

그럼 길을 단축할 수 있는 횟수는 어떻게 구할까? 단순하다. 시작좌표에서 목표좌표까지 대각선으로 몇 칸이나 차이나느냐 이거다. (chance)

이 둘을 비교해서 (chance, ㄱ자거리 - t ) 내 찬스가 더 많으면 목표지점까지 어떻게든 단축시켜서 도달할 수 있다는 뜻이다.

근데 내 찬스가 모자르다면 어떻게서든 기를쓰고 턴을줄이려고 대각선으로 가도 목표지점까지 도달하지 못한다는 뜻이다.

 

마지막 경우가 있다.

ㄱ자로 가는 거리보다 턴이 넉넉한 경우.

이건 무조건 목표지점까지 도달가능하다는 뜻이다. ㄱ자로 가서 남는 턴동안 뱅글뱅글돌다가 마지막에 목표지점에 쏙 들어가면 그만이니까!

 

---

결   과  :

class Solution {
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        // sx, sy에서 시작해 fx, fy까지 t거리만에 갈 수 있는지 없는지 리턴
        // 1거리 이동하는 방향은 8방향
        // 같은 곳을 여러번 방문할 수 있음

        // 일단 start부터 Finish까지 ㄱ자로 가는 거리를 구한다. -> maxDistance
        // 만약 t가 더 작다면 대각으로도 가줘야 한다는 것. (단축해서 가야함)
        // 대각으로 갈 수 있는 기회를 구한다. 이 기회는 Start에서부터 Finish와 같은 선상에 있을 때까지 대각선으로 간 횟수이다.
        // maxDistance > t 인 상황에서 그 차이가 chance보다 작거나 같으면 대각선으로 길을 단축해 Finish에 도달할 수 있단 뜻이다.
        // 만약 maxDistance보다 t가 더 크다면? 좀 빙글빙글 돌다가 가야한다는 뜻이다. 즉, 무조건 갈 수 있다 

        // 만약에 출발지와 도착지가 같은 경우는? -> t가 1만 아니면 무조건 돌아올수 있음 대각선이동, 중복방문도 가능하기 때문에

        int a = Math.abs(fx - sx);
        int b = Math.abs(fy - sy);
        int chance = Math.min(a, b);
        int maxDistance = a + b;

        // 출발지와 도착지의 좌표가 같을 경우
        if(a == 0 && b == 0) {
            if(t != 1) return true;
            else return false;
        }

        // 출발지와 도착지의 좌표가 다를 경우
        if(t < maxDistance) {
            int crossNumber = Math.abs(t - maxDistance); // 대각선으로 가야하는 횟수
            if(crossNumber <= chance) {
                return true;
            }
            else { // 대각선으로 가야하는 횟수가 찬스보다 더 많을 때 -> 도달하지 못하는 상황
                return false;
            }
        }

        return true;

    }
}

 

 

이 문제는 좋은 문제는 아니였던 것 같다. 알고리즘적인 사고가 아니라 아이디어 문제의 경향이 컸다.