[LeetCode] 789. Escape The Ghosts

무한 2D 격자에서 [0,0]에 있는 내가 target까지 가는 동안, 고스트들이 나를 잡지 못하면 true.
나와 고스트는 매 턴 동시에 상하좌우 1칸 이동 또는 정지.

핵심

추격 시뮬레이션을 돌릴 필요가 없다. 답은 맨해튼 거리 비교 한 줄이다.

• 나와 고스트의 속도는 같다(턴당 1칸).
• 고스트가 나를 잡으려면 target 지점에서 나를 기다리는 것이 최선이다. 중간에서 요격하려 해도, 요격 지점까지의 거리가 내 거리보다 짧아야 하는데 그게 가능하면 target까지의 거리도 어차피 짧다.
• 따라서 dist(ghost, target) <= dist(me, target)인 고스트가 하나라도 있으면 실패.
• 동시 도착도 탈출 실패이므로 비교는 > (등호 포함 안 됨).

시작점이 [0,0]이므로 내 거리는 |tX| + |tY|.

코드

function escapeGhosts(ghosts: number[][], target: number[]): boolean {
    let escape = 0
    const [tX, tY] = target
    for(const [gX, gY] of ghosts) {
        const ghostGap = Math.abs(tX - gX) + Math.abs(tY - gY)
        const playerGap = Math.abs(tX) + Math.abs(tY)
        if(ghostGap <= playerGap) return false
    }
    return true
};

시간 O(n), 공간 O(1).

삽질 기록

처음엔 이렇게 썼다.

const playerGap = tX + tY; // 틀림

|tX| + |tY|가 아니라 그냥 더해버렸다. 좌표가 양수인 예제만 주어져서 통과하는 것처럼 보이지만, 음수 좌표에서 깨진다.

ghosts = [[1,0]], target = [-2,0]

• 실제 내 거리: 2, 고스트 거리: 3 → 정답 false가 나와야 하는데
• 버그 버전: playerGap = -2, 고스트 거리 3이 더 크다고 판정 → true

원점 기준 거리라고 좌표를 그대로 쓰면 안 된다. 거리는 항상 절댓값.