Escaping( BOJ 20041 )

문제 : https://www.acmicpc.net/problem/20041

20041번: Escaping

 

문제 파악하기

N명의 경찰이 1명의 도둑을 잡을 수 있는지 여부를 파악하는 문제입니다. 정답이 Yes / No로 나오는 대표적인 결정 문제라고 할 수 있습니다. 경찰과 도둑은 항상 상하좌우 인접한 격자 점으로 이동하며, 번갈아 가며 한 칸씩 움직일 수 있기 때문에 경찰이 먼저 도달하거나 도둑과 함께 동시에 도달하는 위치에서는 항상 경찰이 도둑을 잡을 수 있습니다. 다만, 도둑이 도망갈 수 있는 격자 점은 무한히 넓은 공간이기 때문에 모든 격자 점을 확인할 수 없습니다. 대신, 특정 격자 점을 선택해서 확인할 수 있습니다.

 

문제 해결하기

N명의 경찰 중 결국 중요한 경찰들은 바로 가로/세로 양 끝에 위치한 경찰입니다. 경찰들이 포함된 영역을 사각형으로 그렸을 때, 해당 위치를 도둑이 벗어나게 된다면 경찰은 절대로 도둑을 잡을 수 없습니다. 따라서, 우리는 도둑이 경찰들의 포위망을 벗어나기 위한 마지막 격자 점의 위치까지 도달하는데 걸리는 시간을 각각 구해보면 됩니다. 경찰들의 포위망을 벗어나는 마지막 위치는 그럼 어떻게 찾을 수 있을까요? 

 

도둑은 잡히지 않아야 하기에 항상 최적으로 움직여야 합니다. 그리고 경찰의 포위망을 가장 빨리 뚫기 위해서는 항상 직선으로 움직여야 합니다. 그렇기에 도둑이 잡히는지 여부를 확인하기 위해서는 도둑이 상하좌우 한 방향으로 쭉 움직였을 때, 포위망의 가장자리에서 도둑이 잡히는지 잡히지 않는지 여부를 확인하면 됩니다. 포위망의 가장자리는 결국 경찰들의 x좌표 최솟값/최댓값과 y좌표 최솟값/최댓값을 활용하여 다음과 같이 만들 수 있습니다. 아래에서 (Sx, Sy)는 도둑의 위치를 의미합니다.

왼쪽( x좌표 최솟값, Sy ) / 오른쪽( x좌표 최댓값, Sy ) / 위쪽( Sx, y좌표 최댓값 ) / 아래쪽(Sx, y좌표 최솟값)

 

이렇게 상하좌우 4가지 방향으로 탈출을 시도했을 때, 한 번이라도 탈출에 성공하면 "YES"를, 모두 실패했다면 "NO"를 출력하면 됩니다. 참고로 경찰들의 좌표는 정렬할 필요가 없으며, 단순히 비교해서 먼저 도착하는지 여부를 확인하면 됩니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <vector>
#define MAX 0x7FFFFFFF
#define MIN 0x80000000
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> PAIR;
 
int N;
lint Sx, Sy, xy[2];
vector< PAIR > inp;
 
int block;
lint vmin[2], vmax[2];
vector< PAIR > dst;
 
int main() {
    // init
    for(int k=0;k<2;k++) {
        vmin[k] = MAX;
        vmax[k] = MIN;
    }
    
    // input
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%lld %lld", &xy[0], &xy[1]);
        inp.emplace_back(xy[0], xy[1]);
        
        for(int k=0;k<2;k++) {
            vmin[k] = min( vmin[k], xy[k] );
            vmax[k] = max( vmax[k], xy[k] );
        }
    }
    scanf("%lld %lld", &Sx, &Sy);
    
    // 도둑의 위치가 경찰에서 벗어나있는 경우
    if(Sx<=vmin[0] or Sx>=vmax[0] or Sy<=vmin[1] or Sy>=vmax[1]) block = 0;
    else {
        block = 0;
        
        // 도둑의 목표지점
        dst.emplace_back(vmin[0], Sy);
        dst.emplace_back(vmax[0], Sy);
        dst.emplace_back(Sx, vmin[1]);
        dst.emplace_back(Sx, vmax[1]);
        
        // 도둑보다 목표지점에 빨리 오는 경찰이 있는지 확인하기
        for(int k=0;k<4;k++) {
            lint dx = dst[k].first;
            lint dy = dst[k].second;
            lint Sd = abs(Sx-dx) + abs(Sy-dy);
            
            for(int i=0;i<N;i++) {
                lint d = abs(inp[i].first-dx) + abs(inp[i].second-dy);
                
                if(d <= Sd) {
                    block++;
                    break;
                }
            }
        }
    }
    
    // 출력
    if(block < 4) printf("YES");
    else printf("NO");
}
/*
2
-100 100
100 -100
1 1
ans: YES
*/
 

후기

도둑이 도망갈 수 있는 평면이 무한대라고 하기에 조금 겁 먹었던 문제입니다. 특별한 수식이 아닌, 효율적인 움직임을 떠올리고 문제를 풀 수 있다는 점에서 재미있던 문제입니다. 수학적인 요소에 겁을 먹고 있다거나 그리디 알고리즘을 연습하고 싶은 사람에게 추천하고 싶은 문제입니다.