Google Kick Start 2019A

2019년의 첫 킥스타트 대회! 엄청 쉬울거라고 생각하고 덤볐으나, 놀라울 정도로 망했다ㅠㅠ 어제 기출로 풀어본 작년 Round H보다 훨씬 어렵게 느껴졌다.

오늘은 2번째 문제였던 Parcel을 풀어보자.

Parcel

격자로 된 도시에 0개 이상의 우체국이 위치하고 있다. 이 도시에 최대 1개의 우체국을 새로 배치할 수 있을 때, 각 격자 점에서 가장 가까운 우체국 까지의 거리 중에서 가장 먼 거리를 최대한 줄여보자. (여기서 거리는 $L_{1}$, 즉 맨하탄 거리이다)

이 문제를 그냥 풀려고 하면 도저히 답이 안 나온다. 이건 풀이를 읽기 전에 한번 고민해보는걸 추천!

우선 $L_1$ 거리의 특징을 알아보자. 실생활에서 일반적으로 가장 많이 이용하는 거리는 $L_2$ (유클리디안) 인데, 두 메트릭에서의 ‘원’ (한 점에서부터의 거리가 같은 점의 집합) 을 나타내면 다음과 같다:

이 문제를 풀기 위해서는 위의 $L_1$과 $L_\infty$를 유심히 살펴볼 필요가 있다. $L_1$에서의 ‘원’은 마름모, 즉 네 변의 길이가 같은 사각형이다. 근데, 이건 그냥 마름모가 아니라 정사각형을 45도 돌린 마름모다! 즉 위 그림에서 $L_1$을 45도 돌리면 $L_\infty$ (chebyshev 거리)가 나온다¹.

이제 이 사실을 가지고 문제를 바꿔서 풀어보면 훨씬 쉬워진다. 우선 답인 ‘최대 거리’를 바이너리 서치를 이용해서 구하도록 하자. 최대 거리를 $r$로 고정하면, ‘기존에 존재하는 우체국을 중심으로 하는 반지름 r의 원’ 으로 덮어지는 점과 덮어지지 않는 점을 아래와 같이 분류할 수 있다:

4	3	2	3	4
3	2	1	2	3
2	1	우	1	2
3	2	1	2	3
(r = 2 인 경우)

이제 새로운 우체국이 같은 반지름으로 나머지 (흰색) 점을 모두 덮을 수 있는지를 확인하면 바이너리 서치의 결정 함수를 완성할 수 있다. (개인적으로는 이 결정 함수를 떠올리는 것이 가장 어려울 것이라 생각한다)

일단 45도를 돌리되, 실수 계산을 피하기 위해 $y+x, y-x$로 좌표를 변환해 보자:

        4      
. 3    
. 2 . 2  
. 1 . 1 . 3
. 2 . 우 . 2  
. 1 . 1    
. 2      
      

. : 원래 격자에는 존재하지 않는 점 (스케일링 이슈)

자, 거리가 같은 점의 집합이 정사각형으로 바뀌어서 살펴보기 쉬워졌다!! 이제 여기서 ‘아직 안 덮어진’ 점을 모두 덮는 정사각형의 크기를 찾아서, 이를 다시 반지름과 비교하면 간단하게 완성♪

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define x first
#define y second
#define pb emplace_back
using namespace std;
using ii = pair<int, int>;

int n, m;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int dist[255][255];

vector<ii> get_extreme(int r, vector<ii> & pts)
{
    if (dist[1][1] > 9999) {
        queue<ii> q;
        for (auto& p: pts) {
            q.push(p);
            dist[p.y][p.x] = 0;
        }

        while (!q.empty()) {
            auto p = q.front(); q.pop();
            for (int i = 0; i < 4; i++) {
                ii np{p.x + dx[i], p.y + dy[i]};
                if (np.x < 1 || np.y < 1 || np.x > m || np.y > n)
                    continue;
                int ndist = dist[p.y][p.x] + 1;
                if (ndist < dist[np.y][np.x]) {
                    dist[np.y][np.x] = ndist;
                    q.emplace(np);
                }
            }
        }
    }

    vector<ii> extreme;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            if (dist[i][j] > r)
                extreme.pb(j, i);
    }

    return extreme;
}

bool cover(int r, vector<ii> & pts)
{
    int maxx = -9999, maxy = -9999,
        minx = +9999, miny = +9999;

    vector<ii> && extreme = get_extreme(r, pts);
    for (auto& p: extreme) {
        minx = min(minx, p.x + p.y);
        maxx = max(maxx, p.x + p.y);
        miny = min(miny, p.y - p.x);
        maxy = max(maxy, p.y - p.x);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x = i + j;
            int y = i - j;
            if (r >= max({x - minx, y - miny, maxx - x, maxy - y}))
                return true;
        }
    }

    return false;
}

int solve(vector<ii> & pts)
{
    int le = 0, ri = m + n, ans = ri;
    while (le <= ri) {
        int mid = (le + ri) >> 1;
        if (cover(mid, pts)) {
            ri = mid - 1;
            ans = mid;
        } else {
            le = mid + 1;
        }
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C++) {
        scanf("%d%d", &n, &m);
        memset(dist, 0x77, sizeof dist);

        vector<ii> pts;
        for (int i = 1; i <= n; i++) {
            char f[255]{};
            scanf("%s", f + 1);
            for (int j = 1; j <= m; j++)
                if (f[j] == '1') pts.pb(j, i);
        }

        printf("Case #%d: %d\n", C, solve(pts));
    }
    return 0;
}

이 회전 관계는 2차원에서만 성립한다. ↩