BOJ 1909. 냄새 싫어

▣ 문제 출처  ─  Polish Olympiad in Informatics(POI) 2005/2006 Stage 1의 5번 문제

▣ 알고리즘 분류  ─  DFS / 이분 탐색 / 스위핑 / 기하 / CHT(Convex Hull Trick)

▣ solved.ac 기준 난이도  ─  Diamond IV (개인적으로는 다3 정도라고 생각한다.)

 

 

문제 링크: https://www.acmicpc.net/problem/1909

 

  크기 $S = W_x \times W_y$ 그리드에 $n$개의 '특별한 점'이 주어진다. $(sx,\, sy)$에서 $(tx,\, ty)$로 가는 임의의 경로에 대해, 경로상의 임의의 점과 특별한 점들 사이 거리의 최솟값을 최대화하는 문제다.

 

  일단 최솟값을 최대화하는 건 나중에 생각하기로 하고, 문제를 조금 단순화시켜서 경로 하나가 주어졌을 때 최소 거리를 구하는 것으로 바꿔 보자. 이걸 naive하게 구하면 한 좌표당 $n$개의 점을 검사하고, 경로상에 점이 최대 $S$개 있을 수 있으므로 총 시간 복잡도는 $\mathcal O(nS)$가 될 것이다. 물론 이는 문제를 풀기에는 턱없이 느리다.

 

  그런데 각 점마다 $n$개의 점을 보는 게 아니라, 반대로 $n$개의 특별한 점으로부터 각 좌표까지의 거리를 재 보면 어떨까? 이러면 각 특별한 점으로부터 BFS를 돌리면서 각 좌표까지의 최단 거리를 갱신하는 식으로 최소 거리를 구할 수 있을 것이다. 구체적으로, 주어지는 특별한 점들을 모두 큐(일반 큐든 우선순위 큐든)에 넣어 놓고, 이후 큐가 빌 때까지 다음의 과정을 반복한다: 큐에서 점을 하나 뽑아 이 점의 주위 좌표들과 특별한 점들의 거리를 계산한다. 그 값이 현재 해당 좌표에 저장된 값보다 더 작으면 갱신하여 큐에 넣고, 그렇지 않으면 무시한다. 이 과정을 모두 마치면 각 좌표마다 가장 가까운 특별한 점까지의 거리가 계산된다. 이때 시간 복잡도는 $\mathcal O(S)$ 내지는 $\mathcal O(S \log S)$가 되어 문제를 해결할 수 있다. ……라고 생각했다면 당신은 낚인 것이다!

 

  언뜻 보기엔 맞는 풀이 같은데… 어디가 문제인 것일까? 편의상 BFS를 돌릴 때 전후좌우 4방향으로 돌렸다고 가정하자. 이 경우 BFS를 시행했을 때 각 좌표가 큐에 들어가는 순서는 4방향으로 따졌을 때의 이동거리 순, 즉 특별한 점들로부터의 맨해튼 거리(Manhattan distance) 순이다.

 

[그림 1] 4방향 BFS 풀이의 반례

  위 [그림 1]에서, 점 $X$와 세 특별한 점 $A$, $B$, $C$와의 거리의 최솟값을 구하는 상황을 생각해 보자. (점선은 각 선분들의 수직이등분선이다.) 점 $X$와 가장 가까운 점은 $A$이므로 최소 거리는 $10$이 나와야 마땅하다. 하지만 BFS가 동작하는 과정을 살펴보면, 일단 점 $B$가 점 $A$보다 먼저 $X1$에 도달하고(맨해튼 거리로 더 가까우므로), $X1$에 $B$까지의 거리가 저장된다. 이후 $A$가 $X1$에 도달하지만, 현재 $X1$에 저장되어 있는 거리($=$ $B$까지와의 거리)보다 작지 않아서 갱신도 일어나지 않고, 따라서 큐에 들어가지도 않는다. 마찬가지로 $X2$도 맨해튼 거리가 더 가까운 $C$가(사실 유클리드 거리도 $C$가 더 작다) 먼저 도달하기 때문에 $X2$에 $C$까지의 거리가 저장되고, 이후 $A$가 도달했을 때 갱신 및 큐 삽입이 일어나지 않는다. 이렇게 점 $X$ 주위의 각 방향으로 인접한 점들에 $A$가 도달하여도 큐에 삽입이 안 되어, 결국 점 $A$는 점 $X$에 도달할 수 없게 된다. 그래서 4방향 BFS로 위 경우를 탐색하면, 점 $X$에 대해 정확한 답을 찾을 수 없다!

 

  그러니까 가령 아래 그림처럼 특별한 점 $A$와 $B$가 있어서, $\overline {AX} \ge \overline {BX}$이고 $\overline {AY}$가 최솟값인 경우 BFS 도중에 $B$가 먼저 $X$에 도달하면 이후 $A$에 대해서 갱신(큐 삽입)이 일어나지 않으므로 $A$는 $X$를 넘어 $Y$에 도달할 수 없다.

 

[그림 2] 반례 설명

이런 식으로 $Y$의 모든 방향에서 $A$의 접근이 막히게 되면 $A$에서 $Y$로 절대 도달할 수 없기에 틀린 답이 나오는 것이고, 그 상황을 실현한 것이 바로 위 반례다. 4방향뿐만 아니라 8방향 등에서도 이러한 반례가 분명히 존재하지만, 보다시피 반례 상황이 굉장히 까다로워 실제로 이를 만들기란 쉽지 않다. 문제는 이게 POI 측도 마찬가지였는지(혹은 데이터 제공을 하지 않았는지), 해당 문제에 8방향 BFS 풀이를 제출하면 맞았습니다!!를 받을 수 있다(...). 그래서인지 이 풀이를 정해로 알고 있는 사람도 꽤 되는 듯하다. 당장 이 문제의 풀이를 검색하면 이 방법의 풀이들만 나오는지라…. (실은 이것이 내가 풀이를 쓰게 된 이유기도 하다.)

 

  그렇다면 이 문제를 어떻게 풀어야 할까? 우선 위 풀이에서 BFS 탐색 방향 수를 늘리는 방법이 있다. 방향 수를 늘릴수록 위 상황이 생기기 어렵기 때문이다. 하지만 그만큼 탐색 횟수도 증가하여 실행 시간과 메모리가 제한에 걸릴 수 있기에 커팅을 빡세게 해야 하는 귀찮음이 있고, 방향을 아무리 늘려도 반례가 존재할 수도 있다. 좀 더 좋은 방법은 없을까?

 

  BFS에서 벗어나서, 문제를 수식으로 접근해 보자. $i$번째 특별한 점의 좌표를 $(x_i,\, y_i)$라고 하면, 우리는 임의의 좌표 $(x,\, y)$에 대해 $(x - x_i )^2 + (y - y_i )^2$을 최소로 하는 $i$를 찾는 것이 목표다. 최소라는 건, 달리 말하면 임의의 $j(1 \le j \le n)$에 대해 $(x - x_i )^2 + (y - y_i )^2 \le (x - x_j )^2 + (y - y_j )^2$를 만족하는 것과 같고, 이를 정리해 보면

$$-2x_i x - 2y_i y + x_i^2 + y_i^2 \le - 2x_j x - 2y_j y + x_j^2 + y_j^2$$

가 된다.

 

  여기서 현재 변수가 $x,\, y$로 두 개이므로 하나를 고정시켜 놓고 생각하자. $y$를 상수로 고정시키면, 좌변과 우변은 $x$에 관한 일차함수가 되어, 결국 여러 직선들이 주어질 때 최솟값을 찾는 문제로 바뀌게 된다. 그리고 이는 CHT(Convex Hull Trick)를 이용해서 빠르게 할 수 있다. 구체적으로,

$$f_i (t) = -2x_i t - 2y_i y + x_i^2 + y_i^2 \equiv m_i t + n_i$$

라고 하면 $t=x$일 때 $f_i (t)$의 값이 최소인 $i$가 곧 $(x,\, y)$로부터 가장 가까운 특별한 점이 되고, 그때의 거리(정확히는 거리의 제곱)는 $\displaystyle\min_i {f_i (x)} + x^2 + y^2$이 된다. 이때 기울기 $m_i = -2x_i$가 작아지는 순, 다시 말해 $x_i$의 오름차순으로 직선을 관리하면, 최솟값은 다음과 같이 upper hull의 형태로 나타난다.

 

[그림 3] 기울기가 감소하는 직선들($f_i(t)$)의 최솟값

이때 CHT를 할 때 모든 특별한 점을 고려하면 가능한 $y$의 개수가 $W_y$개, 각 $y$마다 삽입할 직선은 $n$개이며 함수값을 확인할 $x$의 개수가 $W_x$개이므로 $\mathcal O((n + W_x)W_y)$의 시간이 걸린다. 여전히 2초 내에 돌기에는 부담스러운 시간 복잡도다. 그런데 사실, CHT 시에 $n$개의 점 모두를 고려할 필요가 없다! $y$를 고정시키면, 가장 가까운 점이 될 '후보'의 개수가 최대 $W_x$개로 정해지기 때문이다.

 

[그림 4] 고정된 y에 대해 가장 짧은 거리를 구하는 상황

현재 [그림 4]와 같은 상황이라고 하자. 우리는 $y$가 고정된, 빨간 직선 위의 점들에 대해 최소 거리를 계산하고 있고, 이제 그중 점 $X$에 대해 특별한 점들까지의 가장 짧은 거리를 구하려 한다. 이때 점 $2'$은 절대 가장 가까운 점이 될 수 없다. 왜냐하면 점 $2$보다 빨간 직선에서 더 멀기 때문이다. 마찬가지로 점 $1'$과 $3'$ 또한 $X$와 가장 가까운 점이 될 수 없다. 고로 우리는 점 $1$부터 $8$까지 8개의 점만 고려하면 된다. 이는 점 $X$에만 해당되는 것이 아닌, 빨간 가로선 위의 모든 점이 해당되기 때문에 결국 $y=12$에서 CHT를 시행할 때 8개의 직선만 고려하면 된다. 11개에서 8개로 고작 3개 줄여서 뭐 하게? 라고 생각할 수도 있는데, $n$이 최대 $W_x W_y \,(=256)$까지 가능하다는 걸 고려하면 어마어마하게 차이가 난다!

 

  이를 일반화해 보면, 고정된 $y = k$에 대해 각 $x$마다 $y = k$와 가장 가까운 특별한 점은 최대 하나 존재하므로(해당 $x$ 좌표상에 특별한 점이 아예 없을 수도 있다) 최대 $W_x$개의 점들만이 가장 가까운 점의 후보가 될 수 있다. 따라서 각 $y$에 대해 최대 $W_x$개의 직선만 가지고 CHT를 돌리면 된다. 각각의 $y$마다 그러한 후보들을 구하는 것은 $y=1$부터 $y=W_y$까지 증가시키면서 스위핑을 하거나, 적절한 전처리를 통해 $\mathcal O(1)$에 구할 수 있고, 이를 $x$가 증가하는 순으로 구하면서(직선을 기울기 순으로 관리해야 하므로) 해당 후보 $i$에 대한 직선 $f_i (t) = m_i t + n_i$를 CHT 스택에 삽입한다. 이후 다시 $x=1$부터 $x=W_x$까지 돌면서 $t = x$ 쿼리를 날려 주면, 쿼리가 점점 증가하는 형태이므로 한 가로줄상의 모든 점들에 대해 거리의 최솟값을 $\mathcal O(W_x)$에 구할 수 있다. 그러므로 그리드 내의 모든 점들에 대해, 특별한 점과의 최소 거리를 $W_y$번의 선형시간 스택 CHT로 $\mathcal O(S)$만에 모두 계산할 수 있게 된다.

// v[j]    : x좌표가 j인 특별한 점들의 y좌표 (오름차순으로 저장)
// k[j]    : v[j]에서 현재 검사 중인 특별한 점의 y좌표의 index 
// cht     : CHT 용 stack
// d[j][i] : (j, i)와 가장 가까운 특별한 점까지의 거리(의 제곱)


for (i = 1; i <= Wy; ++i) {   // y를 1부터 Wy까지 돌면서, 
    cht.clear();   // 일단 cht 비우고 
    for (j = 1; j <= Wx; ++j) {
        if (!v[j].size()) continue;   // 해당 x좌표에 특별한 점이 없다면 pass 
        if (i >= v[j][k[j]+1]) k[j]++;
        int p = k[j], y = v[j][p];
        if (i - y > v[j][p+1] - i) p++, y = v[j][p];
        // Sweeping을 통해 각 x좌표마다 현재 y좌표에 가장 가까운 점 찾기 -> y  

        cht.insert({-2*j, j*j + y*y - 2*i*y});   // 찾은 점에 대한 직선 삽입 
    }
    for (j = 1; j <= Wx; ++j) d[j][i] = cht.get(j) + i*i + j*j;
    // 다시 x를 1부터 Wx까지 돌리면서 쿼리를 날려 최소 거리 구하기
}

 

  다시 본 문제로 돌아오면, 이제 남은 건 최솟값을 최대화하는 경로를 찾는 부분뿐인데 이는 이분 탐색으로 쉽게 해결할 수 있다. '$(sx,\, sy)$에서 $(tx,\, ty)$로 가는 경로 중 (특별한 점까지의) 최소 거리가 $x$인 경로가 존재하는가?'라는 결정 문제를 세우고 이를 $x$에 대해 이분탐색해 주면 된다. 혹은 다익스트라 비슷하게 구하는 방법도 있고, Union-Find를 이용하는 방법도 있다. 이 부분은 본인의 기호에 따라 작성하면 되겠다. 여튼 나는 이분탐색을 사용하였고, 이때의 전체 시간 복잡도는 $\color{orchid}{\mathcal O(S + S \log X)}$가 된다.

 

  전체 코드는 다음과 같다. (스위핑 시 처리를 간결하게 하기 위해 위 코드를 조금 변형한 부분이 있다.)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int Wx, Wy, mid;
int h, t;
int k[1001], d[1001][1001];
vector<int> v[1001];
typedef struct { int a, b; } Line;
Line l[100003];
bool vis[1003][1003];

double crs(Line x, Line y) {
    return (double)(y.b - x.b) / (x.a - y.a);
}

void insert(Line x) {
    while (t > 1 && crs(l[t-2], l[t-1]) > crs(l[t-1], x)) t--;
    l[t++] = x;
}

int get(int x) {
    while (h + 1 < t && crs(l[h], l[h+1]) <= x) h++;
    return l[h].a * x + l[h].b;
}

void dfs(int x, int y) {
    if (!x || x > Wx || !y || y > Wy) return;
    if (vis[x][y] || d[x][y] < mid) return;
    vis[x][y] = 1;
    for (int i = 0; i < 4; ++i) dfs(x + dx[i], y + dy[i]);
}

int main()
{
    cin.sync_with_stdio(false); cin.tie(NULL);
    int N, sx, sy, tx, ty, i, j;

    cin >> Wx >> Wy;
    cin >> sx >> sy >> tx >> ty >> N;
    while (N--) {
        cin >> i >> j;
        v[i].push_back(j);
    }

    for (i = 1; i <= Wx; ++i) {
        v[i].push_back(-4000);
        v[i].push_back(6000);
        sort(v[i].begin(), v[i].end());
    }

    for (i = 1; i <= Wy; ++i) {
        h = t = 0;
        for (j = 1; j <= Wx; ++j) {
            if (v[j].size() == 2) continue;
            if (i >= v[j][k[j]+1]) k[j]++;
            int p = k[j], y = v[j][p];
            if (i - y > v[j][p+1] - i) p++, y = v[j][p];
            insert({-2*j, j*j + y*y - 2*i*y});
        }
        for (j = 1; j <= Wx; ++j) d[j][i] = get(j) + i*i + j*j;
    }

    int s = 0, e = d[sx][sy];
    while (s < e) {
        mid = s + e + 1 >> 1;
        memset(vis, 0, sizeof(vis));
        dfs(sx, sy);
        if (vis[tx][ty]) s = mid;
        else e = mid - 1;
    }

    cout << s;
    return 0;
}

 

---

 

  추가로, 본 문제는 위에서도 말했듯 데이터가 약하여 잘못된 풀이들도 통과하지만, 비슷한 내용의 아래 문제는 데이터가 상당히 강하게 구성되어 있어서 웬만한 BFS로는 풀리지 않는다. (하지만 이 문제조차 BFS로 뚫으신 분도 있다.^^;;) 냄새 싫어 문제를 풀었다면 이 문제도 한번 도전해 보자!

 

CodeUp 3050. 감자탕 중독 (https://codeup.kr/problem.php?id=3050)

감자탕 중독