[BOJ] 1348번: 주차장

문제 정의

---

백준1348

풀이

---

BFS를 통해 각 차에서 각 주차장까지의 거리를 구한다. 어떤 매칭이 주어졌을 때 모든 차량이 주차장에 주차하는 시간은 해당 매칭에서 거리가 가장 먼 차와 주차장 사이의 거리와 같다. 따라서 차와 주차장을 길이가 각 차와 주차장 사이의 거리와 같은 간선으로 연결한 이분 그래프를 만든 후 길이가 $L$ 이하인 간선들만을 이용하여 이분 매칭 문제를 풀면 된다. 이분 탐색을 통해 완전 매칭이 되게 하는 가장 작은 $L$값을 찾으면 된다.

구현

---

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#define N 100
#define pii pair<int,int>
using namespace std;
int b[N], r, c, M=-1;
vector<pii> g[N];
vector<int> car;
bool visited[N];
char pk[N][N];
map<int, int> parking;
 
bool dfs(int here, int m) {
    if (visited[here]) return false;
    visited[here] = true;
    for (auto e : g[here]) {
        if (e.second<=m&&(b[e.first]==-1||dfs(b[e.first], m))) {
            b[e.first] = here;
            return true;
        }
    }
    return false;
}
 
void bfs(int i) {
    queue<int> q;
    int dy[4] = {0,0,1,-1}, dx[4] = {1,-1,0,0};
    vector<int> dist = vector<int>(r*c, -1);
    dist[car[i]] = 0;
    q.push(car[i]);
    while (!q.empty()) {
        int y = q.front()/c, x = q.front()%c;
        int here = q.front();
        q.pop();
        for (int k=0; k<4; ++k) {
            int ny = y+dy[k], nx = x+dx[k];
            int there = ny*c+nx;
            if (ny<0||nx<0||ny>=r||nx>=c||pk[ny][nx]=='X') continue;
            if (dist[there]==-1) {
                if (parking.count(there)==1) {
                    M = max(M, dist[here]+1);
                    g[i].push_back(make_pair(parking[there], dist[here]+1)); 
                }
                dist[there] = dist[here]+1;
                q.push(there);
            }
        }
    }
}
 
int match(int m) {
    memset(b, -1, sizeof b);
    int size = 0;
    for (int i=0; i<car.size(); ++i) {
        memset(visited, 0, sizeof visited);
        if (dfs(i, m)) ++size;    
    }
    return size;
}
 
int main() {
    scanf("%d%d", &r, &c);
    int cnt=0;
    for (int i=0; i<r; ++i)
        scanf("%s", pk[i]);    
    for (int i=0; i<r; ++i)
        for (int j=0; j<c; ++j) {
            if (pk[i][j]=='C') car.push_back(i*c+j); 
            else if (pk[i][j]=='P') parking[i*c+j] = cnt++;
        }
    for (int i=0; i<car.size(); ++i)
        bfs(i);
    int lo=-1, hi=M+1;
    while (lo+1<hi) {
        int mid = (lo+hi)/2;
        if (match(mid)<car.size()) lo = mid;
        else hi = mid;
    }
    if (match(hi)==car.size()) printf("%d\n", hi);
    else printf("-1\n");
}