취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23930번 문제인 Parcels이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/23930

먼저 각 칸에서 가장 가까운 delivery office까지의 거리를 multisource bfs를 이용해 계산해 두자.

각 칸의 좌표를 45도 회전시키고 원점으로부터의 거리를 $\sqrt{2}$배시켜 새로운 좌표에 대응시켜보자. 이 좌표계에서는 각 칸에 대하여 그 칸의 가장 가까운 delivery office까지의 거리가 어떤 정수 $K$에 대하여 그보다 작거나 같게 하기 위해 설치되어야 하는 새 office의 범위를 축에 평행항 변들로 이루어진 직사각형꼴로 나타낼 수 있다. 따라서 이 직사각형들의 교집합(에 포함되는 원래의 점 = 두 좌표의 합이 짝수인 점)의 존재 여부로 원하는 값이 $K$ 이하가 될 수 있는지 여부를 판단할 수 있게 된다. 

$K$의 값을 이분 탐색으로 계산해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

int R, C;
vector<pair<int, int>> vec[500];
int dist[250][250];
queue<pair<int, int>> que;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
int LL, RR, mx;

int bnsearch() {
    LL = 0, RR = mx;
    while (LL < RR) {
        int mid = (LL + RR) / 2;
        int XL = -1000000007, XR = 1000000007, YL = -1000000007, YR = 1000000007;
        for (int k = mid + 1; k <= mx; k++) {
            for (auto &p:vec[k]) {
                XL = max(XL, p.first - mid);
                XR = min(XR, p.first + mid);
                YL = max(YL, p.second - mid);
                YR = min(YR, p.second + mid);
            }
        }
        if (XL <= XR && YL <= YR) {
            if (XL == XR && YL == YR && (abs(XL + YL) & 1)) LL = mid + 1;
            else RR = mid;
        }
        else LL = mid + 1;
    }
    return LL;
}

void bfs() {
    while (!que.empty()) {
        int r = que.front().first, c = que.front().second; que.pop();
        mx = max(mx, dist[r][c]);
        vec[dist[r][c] - 1].emplace_back(make_pair(r + c, c - r));
        for (int i = 0; i < 4; i++) {
            int rr = r + dr[i], cc = c + dc[i];
            if (rr < 0 || rr >= R || cc < 0 || cc >= C || dist[rr][cc]) continue;
            dist[rr][cc] = dist[r][c] + 1;
            que.push(make_pair(rr, cc));
        }
    }
}
void solve() {
    mx = 0;
    for (int r = 0; r < 500; r++) vec[r].clear();
    cin >> R >> C;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            char x; cin >> x;
            if (x == '1') dist[r][c] = 1, que.push(make_pair(r, c));
            else dist[r][c] = 0;
        }
    }
    bfs();
    cout << bnsearch() << '\n';
}

int T;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": ";
        solve();
    }
}

랜덤 마라톤 · 코스 13 F번