백준 4001번: 미노타우르스 미궁 [C++]

작성일 | In
다이아몬드 IV 다이아몬드 IV

문제

미노타우르스 미궁

풀이

$(w, h)$에서 $(1, 1)$로 갈 수 없다는 것은 왼쪽 혹은 아래쪽 벽이 오른쪽 혹은 위쪽 벽과 이어져 있다는 것과 동치입니다.

그래프 탐색 알고리즘을 통해 왼쪽 혹은 아래쪽 벽과 연결된 칸, 오른쪽 혹은 위쪽 벽과 연결된 칸을 각각 탐색합시다.

장애물을 설치할 수 있는지는 차치하고, 일단 설치했을 떄 미노타우르스가 갇히는지 판단해 봅시다.

장애물을 설치했을 때 $(w, h)$에서 $(1, 1)$로 갈 수 없으려면 장애물의 테두리보다 한칸 더 확장한 직사각형 내에 왼쪽 혹은 아래쪽 벽과 연결된 칸, 오른쪽 혹은 위쪽 벽과 연결된 칸이 모두 존재해야 합니다. 이는 누적 합을 통해 $O(1)$에 판단할 수 있습니다.

이제 이분 탐색을 통해 문제를 해결할 수 있습니다. 모든 좌표 $(i, j)$에 대해 이분 탐색을 통해 미노타우르스를 가둘 수 있는 가장 작은 정사각형 장애물의 크기를 구해줍시다. 실제로 해당 장애물을 설치할 수 있는지는 장애물 개수 누적 합을 이용해서 판단해주면 됩니다.

시간 복잡도는 $O(wh\log \max(w, h))$입니다.

코드

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>
using namespace std;

int dr[] = {0, -1, -1, -1, 0, 1, 1, 1}, dc[] = {1, 1, 0, -1, -1, -1, 0, 1};

int w, h;

bool isInvalid(int row, int col) {
    return row < 1 or col < 1 or row > h or col > w;
}

constexpr int MX = 1515;
char labyrinth[MX][MX];
int ld[MX][MX], ru[MX][MX], obstacle[MX][MX];

void build(int arr[MX][MX], int r, int c) {
    if (r)
        arr[r][c] += arr[r - 1][c];
    if (c)
        arr[r][c] += arr[r][c - 1];
    if (r and c)
        arr[r][c] -= arr[r - 1][c - 1];
}

int getCount(int arr[MX][MX], int r1, int r2, int c1, int c2) {
    int ret = arr[r2][c2];

    if (r1 > 0)
        ret -= arr[r1 - 1][c2];
    if (c1 > 0)
        ret -= arr[r2][c1 - 1];
    if (r1 > 0 and c1 > 0)
        ret += arr[r1 - 1][c1 - 1];

    return ret;
}

void obstacleBfs(pair<int, int> start, int arr[MX][MX]) {
    queue<pair<int, int>> q;
    auto [r, c] = start;
    arr[r][c] = 1;
    q.push(start);

    while (not q.empty()) {
        tie(r, c) = q.front();
        q.pop();

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

            if (isInvalid(nr, nc) or arr[nr][nc] == 1 or
                labyrinth[nr][nc] != '#')
                continue;

            arr[nr][nc] = 1;
            q.emplace(nr, nc);
        }
    }
}

int getMinBlockableSize(int row, int col) {
    int maxSize = min(h - row + 1, w - col + 1);
    if (row + maxSize - 1 == h and col + maxSize - 1 == w)
        maxSize--;

    int lo = 1, hi = maxSize + 1;

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

        if (getCount(ld, row - 1, row + mid, col - 1, col + mid) > 0 and
            getCount(ru, row - 1, row + mid, col - 1, col + mid) > 0)
            hi = mid;
        else
            lo = mid + 1;
    }

    return lo <= maxSize ? lo : -1;
}

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

    cin >> w >> h;

    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> labyrinth[i][j];
            obstacle[i][j] = (labyrinth[i][j] == '#');
        }
    }

    for (int r = 1; r <= h; r++) {
        ld[r][0] = ru[r][w + 1] = 1;

        if (labyrinth[r][1] == '#')
            obstacleBfs({r, 1}, ld);
        if (labyrinth[r][w] == '#')
            obstacleBfs({r, w}, ru);
    }
    for (int c = 1; c <= w; c++) {
        ld[h + 1][c] = ru[0][c] = 1;

        if (labyrinth[h][c] == '#')
            obstacleBfs({h, c}, ld);
        if (labyrinth[1][c] == '#')
            obstacleBfs({1, c}, ru);
    }

    for (int r = 0; r <= h + 1; r++) {
        for (int c = 0; c <= w + 1; c++) {
            build(ld, r, c);
            build(ru, r, c);
            build(obstacle, r, c);
        }
    }

    int l = MX, x, y;

    for (int r = 1; r <= h; r++) {
        for (int c = 1; c <= w; c++) {
            if (r == 1 and c == 1)
                continue;
            if (r == h and c == w)
                continue;
            if (labyrinth[r][c] == '#')
                continue;

            int sz = getMinBlockableSize(r, c);
            if (sz == -1 or
                getCount(obstacle, r, r + sz - 1, c, c + sz - 1) > 0)
                continue;

            if (sz < l) {
                l = sz;
                x = r, y = c;
            }
        }
    }

    if (l == MX)
        cout << "Impossible";
    else
        cout << l << ' ' << y << ' ' << x;

    return 0;
}

백준 4001번: 미노타우르스 미궁 [C++]