[1348] 주차장

https://www.acmicpc.net/problem/1348

1348번: 주차장

<문제>

bfs(전처리) + 이분매칭 + 이분탐색으로 해결할 수 있다.

 

bfs로 'C'의 (R1, C1)에서 'P'의 (R2, C2)까지의 '거리'를 구해준다. 이를 int cost[][]에 저장해주었고,

cost[5][7] = 13이면, 5번째 'C'에서 7번째 'P'까지의 거리는 '13'이다, 라는 의미이다.

'C'와 'P'의 좌표를 항상 필요로 하므로, 입력을 받자마자 'C'와 'P'의 좌표를 별도의 vector에 저장해주었다.

 

이분매칭을 사용하기 위해서, 가중치가 없는 방향그래프를 생성해야 하며, 이는 아래처럼 진행할 수 있다.

cost[i][j] <= 'K' 이면, i->j로 갈 수 있다.

위의 방식대로 모든 가중치 없는 방향 그래프를 생성했다면, 이분매칭을 진행해주면 되겠다.

이분매칭은 특별한 게 없다. 기본적인 이분매칭을 그대로 사용해주고, 'C'의 개수만큼 매칭되면 정답으로 취급한다.

 

C'와 'P'는 같은 좌표에 존재할 수 없으므로, cost[i][j]의 범위는 1부터 50*50정도까지이다.

'K'이하의 가중치를 연결했는데 매칭이 불가능했다면, 'K-1'이하는 정답의 가능성이 완전히 사라진다.

이분탐색을 사용할 수 있는 전형적인 형태이므로, 이분탐색을 진행할 수 있겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}, cost[101][101];
char a[52][52];
typedef struct {
    int y, x;
} state;
vector<int> adj[101];
vector<state> C, P;
void bfs(int sy, int sx, int num) {
    int dist[51][51];
    memset(dist, -1, sizeof(dist));
    queue<state> q;
    q.push({sy, sx});
    dist[sy][sx] = 0;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == 'X' || dist[y][x] >= 0) continue;
            dist[y][x] = dist[cur.y][cur.x] + 1;
            q.push({y, x});
        }
    }
    for (int i = 0; i < P.size(); i++) {
        cost[num][i + 1] = dist[P[i].y][P[i].x];
    }
    return;
}
void makeGraph(int k) {
    int i, j;
    for (i = 0; i <= 100; i++) adj[i].clear();
    for (i = 1; i <= C.size(); i++) {
        for (j = 1; j <= P.size(); j++) {
            if (0 < cost[i][j] && cost[i][j] <= k) {
                adj[i].push_back(j);
            }
        }
    }
    return;
}
bool vst[101];
int d[101];
bool dfs(int cur) {
    for (auto& next : adj[cur]) {
        if (vst[next] == true) continue;
        vst[next] = true;
        if (d[next] == -1 || dfs(d[next]) == true) {
            d[next] = cur;
            return true;
        }
    }
    return false;
}
bool solve(int turn) {
    makeGraph(turn);
    int i, j, cnt = 0;
    memset(d, -1, sizeof(d));
    for (i = 0; i < C.size(); i++) {
        memset(vst, 0, sizeof(vst));
        if (dfs(i + 1) == true) {
            cnt++;
        }
    }
    if (cnt == C.size()) return true;
    return false;
}
int main(void) {
    int i, j;
    cin >> n >> m;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'C')
                C.push_back({i, j});
            else if (a[i][j] == 'P')
                P.push_back({i, j});
        }
    }
    if (C.size() == 0) {
        cout << "0";
        return 0;
    }
    if (C.size() > P.size()) {
        cout << "-1";
        return 0;
    }
    for (i = 0; i < C.size(); i++) bfs(C[i].y, C[i].x, i + 1);
    int l = 0, r = 2501, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (solve(mid) == true) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans;
    return 0;
}