간단한 팩맨 게임을 한다고 상상해 봅시다. 우리는 좌표 (0, 0)에서 출발하여 목적지 (target[0], target[1])에 도달해야 합니다. 맵 위에는 여러 마리의 유령이 있으며, i번째 유령은 (ghosts[i][0], ghosts[i][1])에서 시작합니다. 매 턴마다 우리와 모든 유령은 동시에 북·동·서·남 네 방향 중 하나를 선택해 이동하며, 한 번에 거리 1만큼 움직일 수 있습니다.
탈출에 성공하는 조건은 단 하나, 어떤 유령보다 먼저 목적지에 도착하는 것입니다. 유령이 어떤 경로로 움직이더라도 목표에 먼저 도달할 수 있어야 하며, 만약 유령과 같은 칸(목적지 포함)에 동시에 도착한다면 탈출로 인정되지 않습니다. 따라서 탈출이 가능하면 true, 불가능하면 false를 반환해야 합니다.
문제 예시
예를 들어 유령의 위치가 [[1,0], [0,3]]이고 목적지가 [0,1]이라면 결과는 true입니다. 우리는 시간 1에 목적지 (0, 1)에 곧장 도달할 수 있지만, (1, 0)이나 (0, 3)에 위치한 유령은 그 전에 우리를 가로막을 방법이 없기 때문입니다.
접근 방법
이 문제의 핵심은 맨해튼 거리(Manhattan Distance) 비교입니다. 유령 역시 최적의 경로를 선택해 우리를 막으려 할 것이므로, 다음과 같이 판단할 수 있습니다.
- me := |target[0]| + |target[1]| → 출발점 (0, 0)에서 목적지까지의 맨해튼 거리
- x := |ghosts[i][0] − target[0]| + |ghosts[i][1] − target[1]| → 각 유령에서 목적지까지의 맨해튼 거리
- 어떤 유령의 거리 x가 me보다 작거나 같다면 → 해당 유령은 우리와 동시에 또는 더 빨리 목적지에 도달할 수 있으므로 탈출 불가능
- 모든 유령이 me보다 큰 거리를 가진다면 → true 반환
왜 이것이 성립할까요? 삼각부등식에 의해, 유령이 우리의 경로상 임의의 지점 p에서 우리를 가로막으려면 유령의 p까지의 거리가 우리의 p까지의 거리 이하여야 합니다. 그런데 그 경우 유령의 목적지까지의 거리 역시 우리의 목적지까지의 거리 이하가 됩니다. 따라서 모든 유령이 목적지까지 우리보다 멀리 있다면, 우리는 직선 경로를 따라 안전하게 목적지에 도달할 수 있습니다.
알고리즘 단계
- 목적지까지의 내 맨해튼 거리 me를 계산합니다.
- 모든 유령에 대해 유령→목적지 맨해튼 거리를 계산합니다.
- 그 거리가 me 이하인 유령이 하나라도 있으면 false를 반환합니다.
- 루프가 정상적으로 끝나면 true를 반환합니다.
시간 복잡도는 유령의 수를 n이라 할 때 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
int me = abs(target[1]) + abs(target[0]);
int x = 0;
for(int i = 0; i < ghosts.size(); i++){
x = abs(ghosts[i][0] - target[0]) + abs(ghosts[i][1] - target[1]);
if(x <= me) return false;
}
return true;
}
};
main(){
vector<vector<int>> v1 = {{1,0}, {0,3}};
vector<int> v2 = {0,1};
Solution ob;
cout << (ob.escapeGhosts(v1, v2));
}실행 결과
입력
[[1,0],[0,3]] [0,1]
출력
1
출력값 1은 true, 즉 탈출에 성공했음을 의미합니다.