[BruteForce] 백준 28215, 대피소

 이 문제는 생각보다 description이 길다. 가장 주요하게 보아야 할 부분은 무엇보다 변수 n의 범위가 50이라는 점이다. 그렇다면 이 문제는 O($n^4$)까지 시간복잡도를 가져갈 수 있다는 것을 의미한다. 

 

중요하게 깨달아야 할 부분을 기술해 보겠다. 

1) O($n^4$)의 시간복잡도가 허용되므로, Bruteforce일 가능성이 크다. 

2) 거리가 최소가 될 수 있는 대피소의 위치는 "집"에 설치한다고 명기되어 있다 이 부분을 꼭 잘 캐치해야 한다. 

    즉, 탐색 도메인이 X, Y의 100,000이 아니라 50개의 집의 위치로 좁아지게 된다. 

3) X, Y는 서로 연관이 있기 때문에 완전 독립적으로 풀어서는 안된다. 

4) 시간복잡도를 줄이려고 median값으로 푸는 것도 시도해 볼 수 있다. 그런데 주의해야 할 점은 좌표가 겹치는 경우다. 

   [1,2,5]: median값은 제대로 2가 될 수 있다.

   이런 경우는? [1,2,2,5,5,5,5]: median값이 5가 되어 잘못된 결과를 도출하게 된다. 

 

시간복잡도가 충분하기 때문에 4중 for문으로 formulation할 수 있을 것 같다. 그런데, 대피소의 갯수가 1~3으로 확정되지 않고 유동적으로 움직이기 때문에 이에 대해서 모두 다르게 formulating하면 코드가 너무 복잡해 진다. 코드를 간단하게 하는 팁은 무엇일까? 바로 대피소의 갯수를 3개로 정하고 코드를 짜고, 만약 1개 일 경우에는 3개의 위치를 모두 똑같이 하고, 2개일 경우에는 2개위 위치 index만 동일하게 해주는 것이다. Bruteforce 문제로 단순해 보이지만, 잘못된 접근법을 유지할 경우 해매게 될 수 있는 그런 문제다. 주의하며 풀어보자.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;

int n, k;
vi x, y, xs, ys;
const int INF = 1e9;

// n<=50의 크기는 모든 포인트를 O(n4) 해도 충분한 시간 복잡도이다. 
// p1, p2, p3가 정해졌을 때 가장 최단 거리로 i번째 위치의 거리를 반환하고 그 값의 max를 취한다.
int calc(int p1, int p2, int p3) {
    int ans = 0;
    for(int i=0; i<n; ++i) {
        ans = max(ans, min({abs(x[i]-x[p1]) + abs(y[i]-y[p1]), abs(x[i]-x[p2]) + abs(y[i]-y[p2]), abs(x[i]-x[p3]) + abs(y[i]-y[p3])}));
    }
    return ans;
}

void solve() {
    cin >> n >> k;
    x = vi(n), y = vi(n);
    for(int i=0; i<n; ++i) cin >> x[i] >> y[i];
    
    int ans = INF;
    // 1, 2, 3일 경우를 나누어 3단 for loop 진행
    // 1, 2, 3일 때로 calc함수를 나누어 짜지 않고 간단하게 인자를 동일시 시키는 방법을 택함 
    if(k==1) {
        for(int i=0; i<n; ++i) ans = min(ans, calc(i, i, i));
    }
    else if(k==2) {
        for(int i=0; i<n; ++i) {
            for(int j=i; j<n; ++j) {
                ans = min(ans, calc(i, j,j));
            }
        }
    }   
    else if(k==3) {
        for(int i=0; i<n; ++i) {
            for(int j=i; j<n; ++j) {
                for(int k=j; k<n; ++k) {
                    ans = min(ans, calc(i, j,k));
                }
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    fastio;
    solve();
    return 0;
}