[BOJ] 백준 1348. 주차장 (Platinum II)

생긴 건 되게 bfs 처럼 생겼는데 알고보니 bfs + bipartite matching + binary_search (필수는 아니지만) 가 복합적으로 사용되는 문제였다.

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

1348번: 주차장

---

의식의 흐름 및 해설

하나의 주차장에는 하나의 차만 들어갈 수 있고,

그 외에 이동하면서 차끼리 충돌은 고려하지 않는다. (휴... 정말 다행이다. bfs로 충분히 할 수 있겠다.)

주차장과 차끼리 연결되는 모습이 이분그래프를 그려지므로 이분매칭으로 해결할 수 있겠다는 생각이 들었다.

 

일단 차에서 주차장까지의 시간을 BFS로 찾아낸다.

이 때, O(N^3)의 시간이 소요된다. int visit[101][101]로 설정해준 후, 각 차에 따른 모든 좌표까지의 거리를 visit에 저장해준 후 모든 주차장의 거리를 구해주면 된다. 즉, 차 N대*O(bfs) 이므로 O(N^3)이다.

만약 차 한대와 하나의 주차장까지 구할 때 모두 bfs를 한다면 O(N^4)이고 이것도 100^4=1e8이므로 시간 내에는 된다.

 

또한 R, C<=50이므로 답으로 가능한 최대 시간은 2500이다.

따라서 이분탐색으로 ㄱㄴ? ㄱㄴ? ㅆㄱㄴ 모드로 답을 탐색해준다. (시간 300만에 ㄱㄴ? 시간 150만에 ㄱㄴ?)

참고로 그냥 0~2500까지 비교해봐도 TLE는 나지 않을 듯하다.

이분탐색 내에 이분매칭이 포함되므로 시간은 O(log(2500)*N^2))이다.

 

이분매칭 코드는 아래와 같다.

bool dfs(int cur, int time) {
	for (auto i : v[cur]) {
		if (used[i] || dis[cur][i] > time)
			continue;
		used[i] = true;
		if (d[i] == -1 || dfs(d[i], time)) {
			d[i] = cur;
			return true;
		}
	}
	return false;
}

 

bfs로 구해놓은 차-주차장까지의 시간을 이용해 제한시간을 초과하는 경우 아예 탐색하지도 않게 바꾸어주었다.

이분탐색 코드는 아래와 같다.

	while (s <= e) {
		int mid = (s + e) / 2, ret = 0;
		fill(d, d + 101, -1);
		for (int i = 0; i < car.size(); i++) {
			fill(used, used + 101, false);
			if (dfs(i, mid))
				ret++;
		}
		if (ret == car.size()) {
			ans = mid;
			e = mid - 1;
		}
		else
			s = mid + 1;
	}

매칭이 차량 대수만큼 이루어질 경우 가능한 답이다.

---

테스트케이스 

40%에서 틀린다면 아래 테스트케이스를 참고하자.

3 3
PCC
PCP
CPP
ans: 1

나는 d의 값을 0으로 memset하는 실수를 저질러 40%에서 틀렸었다. (index는 0부터 이뤄지므로 -1로 memset해야 한다. visit이든 d든)

 

아래는 내가 만든 테스트케이스들이다.

3 13
.C.....P.X...
XX.......X..P
XX.....C.....
ans: 6

1 1
.
ans: 0

2 2
PP
PP
ans: 0

3 3
PPP
...
CCP
ans: 2

5 4
...X
X..X
CX..
X..P
PPPP
ans: -1

5 4
X..P
CXXX
..C.
.XXX
PPPP
ans: 4

5 6
.PXX.C
PCP..X
XPX...
CX....
......
ans: 8

3 3
PCC
PCP
CPP
ans: 1

4 4
XPPX
CPXP
CC.C
CPPC
ans: 3

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 51;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int R, C, d[101], dis[101][101], visit[MAX][MAX];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
vector<pi> place, car;
vector<int> v[101];
char a[MAX][MAX];
bool used[101];
void bfs(int x, int y, int idx) {
	queue<pi> q;
	q.push({ x, y });
	visit[y][x] = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < C && ny < R) {
				if (visit[ny][nx] == -1 && a[ny][nx] != 'X') {
					visit[ny][nx] = visit[y][x] + 1;
					q.push({ nx, ny });
				}
			}
		}
	}
	for (int i = 0; i < place.size(); i++) {
		if (visit[place[i].second][place[i].first] == -1)
			dis[idx][i] = INF;
		else {
			v[idx].push_back(i);
			dis[idx][i] = visit[place[i].second][place[i].first];
		}
	}
}
bool dfs(int cur, int time) {
	for (auto i : v[cur]) {
		if (used[i] || dis[cur][i] > time)
			continue;
		used[i] = true;
		if (d[i] == -1 || dfs(d[i], time)) {
			d[i] = cur;
			return true;
		}
	}
	return false;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < C; j++) {
			a[i][j] = s[j];
			if (s[j] == 'C')
				car.push_back({ j, i });
			else if (s[j] == 'P')
				place.push_back({ j, i });
		}
	}
	if (car.size() > place.size()) {
		cout << -1 << "\n";
		return 0;
	}
	for (int i = 0; i < car.size(); i++) {
		memset(visit, -1, sizeof(visit));
		bfs(car[i].first, car[i].second, i);
	}
	int ans = -1, s = 0, e = MAX * MAX;
	while (s <= e) {
		int mid = (s + e) / 2, ret = 0;
		fill(d, d + 101, -1);
		for (int i = 0; i < car.size(); i++) {
			fill(used, used + 101, false);
			if (dfs(i, mid))
				ret++;
		}
		if (ret == car.size()) {
			ans = mid;
			e = mid - 1;
		}
		else
			s = mid + 1;
	}
	cout << ans << "\n";
}

---

구현이 좀 빡센 편이지만, 아이디어 자체를 떠올리긴 어렵지 않아 괜찮은 문제였다.