[백준 5925] Cow Beauty Pageant

생각보다 난감했던 문제.

1. 풀이

문제에서는 3덩이를 이지만, 먼저 2덩이를 잇는 최단 경로를 어떻게 구할까를 생각해보았다.

2덩이에 대해 포함하는 모든 정점들끼리 이어보았을 때 맨헤튼 거리가 제일 짧은 것이 최단 경로가 될 것이다.

그렇다면 이 아이디어를 그대로 적용해 1, 2, 3번 덩어리가 있을 때, 1->2, 1->3, 2->3 이렇게 두 덩이를 잇는 모든 경우의 수를 해볼 수 있다.

하지만 먼저 2덩이를 잇고 그 사이의 경로에서 나온 경로가 나머지 덩어리를 이을 때 최단경로가 나오는 경우는 고려하지 않았다. 이에 대한 반례는 아래와 같다.

5 5

XX...

.....

...XX

.....

XX...

이 경우는 어떻게 고려해줄 수 있을까?

어떤 2덩이를 있는 정점 $(sx,sy),(ex,ey)$가 있다. 이 사이에 있는 모든 맨헤튼 경로는 최단 경로가 된다. 그러면 그 최단 경로 중 한개의 정점에서 나머지 정점을 잇는 다면 위의 경우도 고려해줄 수 있게 된다.

어떤 2덩이를 있는 정점의 최단경로인 좌표를 모두 구해준 뒤, $(sx ex,sy ey)$의 좌표에서 나머지 덩이의 모든 정점들 중 최단경로를 고려해주면 된다.

시간 복잡도는 $O(N4)$가 나온다.

2.소스 코드

#include <bits/stdc++.h>


using namespace std;


typedef pair<int, int> pi;
#define x first
#define y second


struct Line {
    pi s, e;
};


//1->2, 2->3, 1->3
vector<Line> route[3];
int len[3];


int ans;
int n, m;
bool vit[51][51];
string field[51];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };


vector<vector<pi>> comp;
void dfs(pi pos, vector<pi>& arr) {
    vit[pos.x][pos.y] = true;
    arr.push_back(pos);
    for (int i = 0; i < 4; i++) {
        pi np = { pos.x + dx[i], pos.y + dy[i] };
        if (np.x < 0 || np.y < 0 || np.x >= n || np.y >= m) continue;
        if (vit[np.x][np.y] || field[np.x][np.y] == '.') continue;
        dfs(np, arr);
    }
}


int dst(pi a, pi b) { return abs(a.x - b.x) + abs(a.y-b.y); }\
void setlen(int num, int a, int b) {
    for(pi& u : comp[a])
        for (pi& v : comp[b]) {
            if (dst(u, v) - 1 < len[num]) {
                len[num] = dst(u, v) - 1;
                route[num].clear();
            }
            if (dst(u, v) - 1 == len[num])
                route[num].push_back({u, v});
        }
}


void solve(int from, int to) {
    for (Line& u : route[from]) {
        int sx = min(u.s.x, u.e.x);
        int ex = max(u.s.x, u.e.x);


        int sy = min(u.s.y, u.e.y);
        int ey = max(u.s.y, u.e.y);
        for (int i = sx; i <= ex; i++)
            for (int j = sy; j <= ey; j++)
                for (pi& p : comp[to])
                    ans = min(ans, len[from] + dst({ i, j }, p) - 1);
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);


    memset(len, 0x3f3f3f3f, sizeof(len));


    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> field[i];


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vit[i][j] || field[i][j] == '.') continue;
            vector<pi> route;
            dfs({ i, j }, route);
            comp.push_back(route);
        }
    }


    setlen(0, 0, 1);
    setlen(1, 1, 2);
    setlen(2, 0, 2);


    vector<int> temp = {len[0], len[1], len[2]};
    sort(temp.begin(), temp.end());
    
    ans = temp[0] + temp[1];


    solve(0, 2);
    solve(1, 0);
    solve(2, 1);


    cout << ans;


    return 0;
}