PS
[BOJ] 1348번: 주차장
IQLUSION
2020. 4. 12. 19:39
문제 정의
풀이
BFS를 통해 각 차에서 각 주차장까지의 거리를 구한다. 어떤 매칭이 주어졌을 때 모든 차량이 주차장에 주차하는 시간은 해당 매칭에서 거리가 가장 먼 차와 주차장 사이의 거리와 같다. 따라서 차와 주차장을 길이가 각 차와 주차장 사이의 거리와 같은 간선으로 연결한 이분 그래프를 만든 후 길이가 $L$ 이하인 간선들만을 이용하여 이분 매칭 문제를 풀면 된다. 이분 탐색을 통해 완전 매칭이 되게 하는 가장 작은 $L$값을 찾으면 된다.
구현
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #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"); } | cs |