[백준] 1348 주차장.
문제
세준 주차장은 R×C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다.
보통 모든 차는 현재 위치에서 가장 가까운 위치에 있는 주차 구역에 주차를 하려고 한다. 하지만, 다음과 같이 생긴 주차장이라면 현재 위치에서 가장 가까운 위치에 주차하는 것이 비효율적이다.
.C.....P.X...
XX.......X..P
XX.....C.....‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다.
만약 아래에 있는 차가 현재 위치에서 가장 가까운 곳에 주차를 한다면, 왼쪽 위에 있는 차는 가장 오른쪽에 있는 주차 구역에 주차를 해야 할 것이다. 이렇게 되면, 그 차가 주차하기 까지 14라는 시간이 걸린다. 하지만, 만약 아래에 있는 차가 오른 쪽에 있는 주차 구역에 주차를 하게 된다면, 두 차가 주차하기 까지 6이라는 시간이 걸린다.
현재 주차장의 모양과, 차의 위치, 주차 구역의 위치가 주어졌을 때, 모든 차가 주차하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 차는 매우 작기 때문에, 한 칸에 여러 대의 차가 동시에 들어갈 수 있다. 차는 빈 공간과, 주차 구역만 통과할 수 있지만, 벽은 통과할 수 없다.
만약 모든 차가 주차하는 것이 불가능하다면, -1을 출력한다.
입력
첫째 줄에 주차장의 세로 크기 R과 가로 크기 C가 주어진다. R과 C의 크기는 50보다 작거나 같다. 둘째 줄부터 R개의 줄에는 주차장의 정보가 주어진다. 주차장의 정보는 문제에서 설명한 문자로 이루어져 있다. 차의 개수와, 주차 구역의 개수는 모두 0보다 크거나 같고 100을 넘지 않는다.
출력
첫째 줄에 모든 차가 주차하는데 걸리는 시간의 최솟값을 출력한다. 차가 없는 경우는 0을 출력한다.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
vector<pi>cars;
vector<pi>parks;
vector<pi>d[101];
int R, C, v[101], parked[101], dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
char mp[51][51];
vector<pi> bfs(pi k) { //k번째 자동차에 대해서 모든 주차장까지의 거리를 반환함
vector<pi>dist;
int visited[51][51];
memset(visited, 0, sizeof(visited));
queue<pi>q;
q.push(k);
visited[k.first][k.second] = 1;
while (!q.empty()) {
auto [y, x] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= 0 && ny < R && nx >= 0 && nx < C) {
if (!visited[ny][nx] && mp[ny][nx] != 'X') {
visited[ny][nx] = visited[y][x] + 1;
q.push({ ny,nx });
if (mp[ny][nx] == 'P') { //만약 주차장을 발견하면
for (int j = 1; j < parks.size(); j++) { //모든 주차장에 대해서 몇번째 주차장인지 검색
if (ny == parks[j].first && nx == parks[j].second) {
dist.push_back({ visited[ny][nx]-1, j }); //{거리, 인덱스}를 dist에 저장
break;
}
}
}
}
}
}
}
sort(dist.begin(), dist.end()); //거리순으로 소트
return dist;
}
bool dfs(int k,int time) { //이분매칭
for (auto [cost, idx] : d[k]) {
if (v[idx] || cost>time) continue;
v[idx] = 1;
if (!parked[idx] || dfs(parked[idx], time)) { //idx번째 주자장에 차가 없으면
parked[idx] = k; //k번째 차가 주차
return true;
}
}
return false;
}
bool check(int time) {
memset(parked, 0, sizeof(parked));
for (int i = 1; i <cars.size(); i++) {
memset(v, 0, sizeof(v));
if (!dfs(i, time))return false;
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
char c;
cin >> R >> C;
cars.push_back({ -1,-1 }); //자동차 0번째 인덱스
parks.push_back({ -1,-1 }); //주차장 0번째 인덱스
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> mp[i][j];
if (mp[i][j] == 'C') {
cars.push_back({ i,j }); //자동차 1번부터 저장
}
if (mp[i][j] == 'P') {
parks.push_back({ i,j }); //주차장 1번부터 저장
}
}
}
if (cars.size() == 1) { //자동차가 없으면 0
cout << 0;
return 0;
}
if (cars.size() > parks.size()) { //자동차가 주차장보다 많으면 -1
cout << -1;
return 0;
}
for (int i = 1; i < cars.size(); i++) { //d[i] : i번째 자동차가 주차할 수 있는 주차장과 거리를 저장 {거리,주차장 인덱스} (sorted 됨)
d[i] = bfs(cars[i]);
}
int le = 0, ri = R * C, mid, ans = INT_MAX;
while (le<=ri) {
mid = (le + ri) / 2;
if (check(mid)) {
ans = min(ans, mid);
ri = mid - 1;
}
else
le = mid + 1;
}
ans != INT_MAX ? cout << ans : cout << -1;
}단순한 이분매칭 문제인줄 알고 덤볐다가......................하나 배워간 문제입니다.
이분매칭 알고리즘만 사용해서는 최솟값을 찾지 못합니다.
자리가 필요해 비켜줄 수 있으면 무조건 비켜주기때문에....
시간이 늘어나면 비켜주면 안되는데 다른 알고리즘이 필요합니다.
따라서 이분탐색이 필요합니다.
사실 이분탐색을 사용할 뻔한 문제입니다 왜냐하면 조건이 존재하고, 그 조건을 만족하는 최솟값을 찾는 문제이기 때문입니다.
모든 자동차를 주차할 수 있을때, 최소 시간을 구하라.
전형적인 이분탐색 문제입니다.
우선 지도가 주어졌으므로, 모든 자동차에 대해, 모든 주차장의 거리를 저장해야합니다.
1.BFS를 자동차 i 에대해 수행해서, 벡터 d[i]에 저장합니다
d[i]는 자동차 i에서 접근할 수 있는 모든 주차장의 인덱스와 거리를 저장합니다.
2.이분탐색을 이용해서 시간 K가 걸릴때, 모든 주차장에 차를 주차할 수 있는지 확인합니다.
3. 이때 모든 주차장에 차를 주차할 수 있는지 확인하기 위해 이분매칭을 사용합니다.
이분매칭의 알고리즘은 다음과 같습니다.
만약 이미 방문했거나, 시간K보다 주차하는데 오래걸리는 주차장은 넘어갑니다.
비어있는 주차장을 발견하거나, 기존 주차한 차가 다른 주차장에 K시간 내에 주차할 수 있다면 주차합니다. True를 반환합니다.
주차하지 못했다면 False 를 반환합니다.