커다란 도시( BOJ 25380 )

문제 : https://www.acmicpc.net/problem/25380

25380번: 커다란 도시

 

문제 파악하기

K명의 경찰이 서로를 만나기 위해 필요한 이동거리의 합의 최솟값을 구하는 문제입니다. 경찰들은 주어진 길을 통해서만 움직일 수 있기에 모든 경로가 최단 경로(맨해튼 경로)가 아닐 수 있습니다. 그렇다고 한 명씩 확인하기에는 최대 200,000명의 경찰 사이의 경로를 확인해야 하기에 제한시간 이내에는 불가능합니다. 이렇게 복잡한 문제는 단계를 나눠서 생각하면 알고리즘을 구상하는데 도움이 됩니다. 다행히 정올에는 서브태스크가 주어지기 때문에 각각의 단계를 하나씩 해결하면서 알고리즘을 개선할 수 있습니다. 그럼 한 단계씩 확인해봅시다.

 

문제 해결하기

우선, 문제를 작게 분할해봅시다. 이 문제에서 가장 먼저 확인할 중요한 점은 이동거리 계산 시, x값과 y값이 독립적으로 계산된다는 점입니다. 2명의 경찰 사이의 거리는 x값이 차이와 y값이 차이의 합으로 계산되며, 따라서 우리는 x값과 y값을 따로 처리해도 상관없다는 걸 유추할 수 있습니다. 그럼 우선 x값과 y값을 따로 저장해봅시다.

 

입력 값을 적절하게 저장했으면 이제는 알고리즘을 구상할 차례입니다. 문제를 해결하는 알고리즘을 떠올리기 위해서는 가장 간단한 경우부터 생각하면 편합니다. 만약 모든 경찰이 두 도로가 교차하는 위치에 서있다면 어떨까요? 이 경우에는 모든 경찰 사이의 이동경로는 맨해튼 경로가 되며, 이 경우에 모든 경찰 사이의 이동거리를 구하는 건 어렵지 않습니다. 현재 값(x값 or y값)을 기준으로 작은 값은 모두 현재 값에서 빼주고, 큰 값은 큰 값에서 현재 값을 빼주면 됩니다.

 

이동 거리 = (현재 값 - 작은 값) + (큰 값 - 현재 값)

 

그리고 이 계산을 효율적으로 하기 위해서는 정렬 및 누적합의 개념을 도입하면 됩니다. 입력된 값을 정렬한 다음, 누적합을 구해놓으면 위 수식을 O(1)만에 구할 수 있습니다. 만약 현재 값의 위치가 (idx)라고 가정하면 위의 수식은 다음과 같이 바꿀 수 있습니다. 다만, 우리는 위에서 x값과 y값을 따로 저장했기 때문에 각각의 값은 따로 계산해야 한다는 점은 기억해야 합니다.

 

d = ( inpX[idx]*(idx-1) - pSum[idx-1] ) + ( (pSum[N]-pSum[idx]) - inpX[idx]*(N-idx) )

 

이렇게 모든 경찰들이 가진 x값과 y값에서 거리를 구한 다음, 2로 나눈 값을 저장하면 모든 경찰 사이의 맨해튼 거리의 합을 구할 수 있습니다. 2로 나눠주는 이유는 모든 정점마다 자신을 제외한 모든 정점 사이의 경로를 구하면서 중복으로 계산된 값을 제외해준 것입니다. 이렇게 맨해튼 거리의 합을 구했다면 100점 중 11점을 획득할 수 있습니다.

 

이 다음, 우리가 생각할 점은 맨해튼 거리로 이동하지 않았을 때, 누락된 경로를 구하는 방법입니다. 예를 들어 문제에 제시된 예시 속 (-4, -1) 위치의 경찰과 (3, -2) 위치의 경찰 사이의 거리를 보도록 하겠습니다. 이 경우, 두 경찰은 맨해튼 경로로 이동할 수 없습니다. 이 경우에는 [ y=-4 ]의 길을 활용하여 조금 돌아가야하며, 이 때 거리가 4만큼 늘어나게 됩니다. 우리는 이렇게 늘어나는 거리를 구해야합니다. 그럼 언제 맨해튼 경로로 이동할 수 없을까요? 바로 이동하려는 두 정점 사이에 길이 없을 때를 의미합니다. (a, b)와 (c, d) 위치에 경찰이 있다고 가정해보겠습니다. 만약 a <= t <= c를 만족하는 [ x=t ]의 길이 있다면 두 경찰은 효율적으로 만날 수 있습니다. 물론 b<=tt<=d를 만족하는 [ y=tt ]의 길이 있는 경우에도 마찬가지입니다. 하지만 [ x=t ]와 [ y=tt ] 같은 길이 없다면 두 경찰관은 조금 돌아가서 만나야 합니다. 우리는 이렇게 두 숫자 사이에 길이 있는지 확인해야 하며, 이 때 이분탐색을 활용할 수 있습니다.

 

이분탐색을 활용하여 만약 (a, b)에서 (c, d)로 이동할 수 있는 길이 모두 있다면 그대로 넘어가면 됩니다. 하지만 길이 없어서 돌아가야 한다면 추가 거리가 발생하며, 추가 거리를 계산할 때에도 역시 이분탐색을 활용하여 돌아갈 길을 선택할 수 있습니다. 한 정점에서 선택할 수 있는 길의 종류는 많지만 효율적으로 처리하기 위해서는 현재 위치를 감싸고 있는 2개의 길 중 하나를 선택하면 됩니다. 여기서 감싸고 있다는 의미는 위/아래 혹은 오른쪽/왼쪽에 위치한 길을 의미하며, 각각의 위치에서 오른쪽과 왼쪽 혹은 위쪽과 아래쪽에 위치한 길을 찾아서 전체 비용이 더 작은 길을 선택하면 됩니다. 그리고 이 경우 또한 누적합을 활용하면 훨씬 빠르고 효율적으로 돌아가는 비용을 계산할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <set>
#include <utility>
#include <algorithm>
#define NMAX 100010
#define PAIR pair<int, int>
#define lint long long int
using namespace std;
 
int N, M, K, x, y;
lint police[2][NMAX*2];
set< lint > road[2];
 
int l, r;
int idx, idxL, idxR;
lint c, ret, tmp;
lint pSum[2][NMAX*2];
 
int policeSearch(lint val, int i, int f) {
    int l, r, mid;
    
    l = 1; r = K;
    while(l<=r) {
        mid = (l+r)/2;
        
        if(police[i][mid] < val) l = mid+1;
        else r = mid-1;
    }
    
    if(police[i][l] == val) return l;
    else if(f == 0) return l;
    else return r;
}
 
int main() {
    // input
    scanf("%d %d %d", &N, &M, &K);
    for(int i=1;i<=N;i++) {
        scanf("%d", &x);
        road[0].insert(x);
    }
    for(int i=1;i<=M;i++) {
        scanf("%d", &y);
        road[1].insert(y);
    }
    for(int j=1;j<=K;j++) scanf("%lld %lld", &police[0][j], &police[1][j]);
    
    // algorithm
    // (1) x좌표, y좌표마다 정렬하여 누적합 구하기
    // (2) 모든 좌표 사이의 맨하탄 거리 구하기
    // (3) 각각의 좌표에 길이 있는지 여부 확인
    //   (3-1) 길이 있는 경우 : 넘어가기
    //   (3-2) 길이 없는 경우 : 다른 정점으로 이동하기 위해 가야하는 길이 만큼 더하기
    
    // (1) 경찰의 x좌표와 y좌표 정렬하여 누적합 구하기
    for(int i=0;i<2;i++) {
        sort(police[i]+1, police[i]+K+1);
        for(int j=1;j<=K;j++) pSum[i][j] = pSum[i][j-1] + police[i][j];
    }
    
    // (2) 모든 좌표 사이의 맨하탄 거리 구하기
    for(int i=0;i<2;i++) {
        for(int j=1;j<=K;j++) {
            // 왼쪽 : police[i][j]*(j-1) - pSum[i][j-1]
            // 오른쪽 : (pSum[i][K]-pSum[i][j]) - police[i][j]*(K-j)
            tmp += (police[i][j])*(j-1) - pSum[i][j-1] + (pSum[i][K]-pSum[i][j]) - police[i][j]*(K-j);
        }
    }
    ret += tmp/2;
    
    // (3) 각각의 좌표에 길이 있는지 확인하기
    for(int i=0;i<2;i++) {
        for(int j=1;j<=K;j++) {
            // 이동할 수 있는 길 찾기 >> 길이 있다면 추가 비용 발생X
            if(road[i].find(police[i][j]) != road[i].end()) continue;
            
            // 최솟값과 최댓값 찾기
            set< lint >::iterator roadL = road[i].lower_bound(police[i][j]);
            if(roadL != road[i].begin()) roadL--;
            
            set< lint >::iterator roadR = road[i].upper_bound(police[i][j]);
            if(roadR == road[i].end()) roadR--;
            
            
            // 기준이 되는 값(criterion) > 해당되는 범위 구하기
            c = *roadR - (police[i][j]-*roadL);
            
            // 기준값(c)과 (*roadL), (*roadR)의 인덱스 값 구하기
            idx = policeSearch(c, i, 1);
            idxL = policeSearch(*roadL, i, 0);
            idxR = policeSearch(*roadR, i, 1);
            if(idxL > idxR) continue;
            
            /*
            // 브루트포스 >> 56점
            if(roadL == roadR) {
                if(j <= idxR) idxL = 1;
                else idxR = K;
            }
            
            for(int k=idxL;k<=idxR;k++) {
                if(k == j) continue;
                
                if(k <= idx) ret += min( abs(police[i][j]-(*roadL)), abs(police[i][k]-(*roadL)) );
                else ret += min( abs((*roadR)-police[i][j]), abs((*roadR)-police[i][k]) );
            }
            */
            
            // 구간이 나눠지지 않음 > 맨 끝 or 맨 위
            if(roadL == roadR) {
                // [ 1 <= j <= idxR ]
                if(j <= idxR) {
                    // 1 ~ (j-1)
                    ret += ((*roadR)-police[i][j])*(j-1);
                    
                    // (j+1) ~ idxR
                    ret += (*roadR)*(idxR-j) - (pSum[i][idxR]-pSum[i][j]);
                }
                // [ idxL <= j <= K ]
                else {
                    // idxL ~ (j-1)
                    ret += (pSum[i][j-1]-pSum[i][idxL-1]) - (*roadL)*(j-idxL);
                    
                    // (j+1) ~ K
                    ret += (police[i][j]-(*roadL))*(K-j);
                }
            }
            
            // 구간이 나눠짐 > 중간
            else {
                // [idxL <= j <= idx <= idxR ]
                if(j <= idx) {
                    // idxL ~ (j-1)
                    ret += (pSum[i][j-1]-pSum[i][idxL-1]) - (*roadL)*(j-idxL);
                    
                    // (j+1) ~ idx
                    ret += (police[i][j]-(*roadL))*(idx-j);
                    
                    // (idx+1) ~ idxR
                    ret += (*roadR)*(idxR-idx) - (pSum[i][idxR]-pSum[i][idx]);
                
                }
                
                // [idxL <= idx <= j <= idxR]
                else {
                    // idxL ~ idx
                    ret += (pSum[i][idx]-pSum[i][idxL-1]) - (*roadL)*(idx-idxL+1);
                    
                    // (idx+1) ~ (j-1)
                    ret += ((*roadR)-police[i][j])*(j-1-idx);
                    
                    // (j+1) ~ idxR
                    ret += (*roadR)*(idxR-j) - (pSum[i][idxR]-pSum[i][j]);
                }
            }
        }
    }
    
    
    printf("%lld", ret);
}
/*
2 2 4
-4 3
2 -4
-4 2
-4 -4
3 2
3 -4
ans: 52
*/
 

후기

많은 기법이 필요하지 않지만 문제를 적절하게 분해하여 알고리즘을 개선해나가는 방식이 필요한 문제입니다. 특히 이분 탐색과 누적합의 개념이 확실하게 있지 않으면 해결하는데 난항을 겪을 것으로 예상합니다. 정올과 같이 실전 대회를 준비하는 사람에게 소개하고 싶은 문제입니다.