백준 2842번: 집배원 한상덕 [C++]

작성일 | In
플래티넘 IV 플래티넘 IV

문제

집배원 한상덕

풀이

상덕이가 고도 $h$가 $m \le h \le M$인 칸만 갈 수 있다고 했을 때, 상덕이가 모든 집에 배달할 수 있는지 너비 우선 탐색을 이용하여 $\mathcal{O}(N^2)$에 판단할 수 있습니다.

모든 $m$에 대해 가능한 가장 작은 $M$을 이분 탐색을 통해 찾을 수 있습니다. 고도로 가능한 값은 최대 $N^2$개 있으므로 각 $m$마다 $\log_2 N^2$번만 시도하면 $M$의 최솟값을 찾을 수 있습니다.

시간 복잡도는 $\mathcal{O}(N^4\log_2 N^2)$ 입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif
using namespace std;

constexpr int deltaRow[] = {0, -1, -1, -1, 0, 1, 1, 1},
              deltaCol[] = {1, 1, 0, -1, -1, -1, 0, 1};

int N;
char village[55][55];
int height[55][55];

pair<int, int> postOffice(-1, -1);

int deliveryCnt = 0;

bool canDelivery(int minHeight, int maxHeight) {
    int officeHeight = height[postOffice.first][postOffice.second];
    if (officeHeight < minHeight or officeHeight > maxHeight)
        return false;

    vector<vector<bool>> visited(N, vector(N, false));
    queue<pair<int, int>> q;

    visited[postOffice.first][postOffice.second] = true;
    q.push(postOffice);

    int remainDelivery = deliveryCnt;

    while (not q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        if (village[r][c] == 'K')
            remainDelivery--;

        for (int k = 0; k < 8; k++) {
            int nr = r + deltaRow[k];
            int nc = c + deltaCol[k];

            if (nr < 0 or nr >= N or nc < 0 or nc >= N)
                continue;
            if (visited[nr][nc])
                continue;
            if (height[nr][nc] < minHeight or height[nr][nc] > maxHeight)
                continue;

            visited[nr][nc] = true;
            q.push(pair(nr, nc));
        }
    }

    return remainDelivery == 0;
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> village[i];

        for (int j = 0; j < N; j++) {
            if (village[i][j] == 'K')
                deliveryCnt++;
            if (village[i][j] == 'P')
                postOffice = pair(i, j);
        }
    }

    vector<int> allHeights;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> height[i][j];
            allHeights.push_back(height[i][j]);
        }
    }

    sort(allHeights.begin(), allHeights.end());
    allHeights.erase(unique(allHeights.begin(), allHeights.end()), allHeights.end());

    int ans = allHeights.back() - allHeights.front();
    for (int i = 0; i < allHeights.size(); i++) {
        int lo = i, hi = allHeights.size();

        while (lo < hi) {
            int mid = (lo + hi) / 2;

            if (canDelivery(allHeights[i], allHeights[mid]))
                hi = mid;
            else
                lo = mid + 1;
        }

        if (lo == allHeights.size())
            continue;

        ans = min(ans, allHeights[lo] - allHeights[i]);
    }

    println("{}", ans);

    return 0;
}

백준 2842번: 집배원 한상덕 [C++]