[BAEKJOON] 1348번 주차장

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

문제조건

1. R x C 모양의 주차장
2. N개의 차와, M개의 주차 구역
3. 차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다.
4. ‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다.
5. 한 칸에 여러 대의 차가 동시에 들어갈 수 있다. 
6. 모든 차가 주차하는데 걸리는 시간의 최솟값을 구하시오.

접근방법

 

단순하게 BFS를 이용해서 탐색하면 되는 문젠줄 알았는데, 전혀 그렇게 풀리지 않는다. 일반적인 구현문제가 아니라 특수한 알고리즘이 필요한 문제다,,, 

 

Bipartite matching

 

이분매칭이라는 알고리즘이 필요하다. 주차구역과 차를 연결해주면서 짝을짓고, 짝을 짓는 경우의 수에 따라 최솟값을 비교하기 위해서이다.

https://yjg-lab.tistory.com/209

[알고리즘] 이분 매칭 알고리즘 (Bipartite Matching)

이분매칭에 대해서 잘 쓰여진 글이 있어서 가지고 왔다. 많은 도움을 얻었다,,!

 

이분매칭에 사용될 {차} - {주차공간} 그룹을 나누기 위해서 BFS로탐색을 진행하며 벡터에 저장해놨고, 그걸 DFS로 이분매칭에 활용했다. 최솟값을 구하는게 목적이므로 이분탐색을 이용해서 계산했다. 

 

소스코드

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int r, c;
int tmp[51][51], dist[101][101], match[101], visited[101];
char map[51][51];
vector<int> edge[101];
vector<pair<int, int> > car, park;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

void bfs(int y, int x, int idx) {
	queue<pair<int, int> > q;
	q.push({ y,x });
	tmp[y][x] = 0;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		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) continue;
			if (tmp[ny][nx] == -1 && map[ny][nx] != 'X') {
				tmp[ny][nx] = tmp[y][x] + 1;
				q.push({ ny,nx });
			}
		}
	}
	for (int i = 0; i < park.size(); i++) {
		if (tmp[park[i].first][park[i].second] == -1) dist[idx][i] = 987654321;
		else {
			//방문했으면 차 - 주차공간 시간 기록, 연결도 기록
			dist[idx][i] = tmp[park[i].first][park[i].second];
			edge[idx].push_back(i);
		}
	}
}

bool judge(int cur, int time) {
	// 한 차에서 가능한 주차공간 모두 탐색하면서 차 - 주차공간 짝지어줌
	for (auto i : edge[cur]) {
		if (visited[i] == 1 || dist[cur][i] > time) continue;
		visited[i] = 1;
		if (match[i] == -1 || judge(match[i], time)) {
			match[i] = cur;
			return true;
		}
	}
	return false;
}

void search() {
	int left = 0;
	int right = 51*51;
	int res = -1;
	while (left  <= right) {
		int mid = (left + right) / 2;
		int cnt = 0;
		fill(match, match + 101, -1);
		for (int i = 0; i < car.size(); i++) {
			fill(visited, visited + 101, 0);
			if (judge(i, mid)) cnt++;
		}
		if (cnt == car.size()) {
			res = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}
	cout << res;
}

int main(){
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < c; j++) {
			map[i][j] = s[j];
			if (map[i][j] == 'C') car.push_back({ i,j });
			else if (map[i][j] == 'P') park.push_back({ i,j });
		}
	}
	if (car.size() > park.size()) {
		cout << -1;
		return 0;
	}
	for (int i = 0; i < car.size(); i++) {
		memset(tmp, -1, sizeof(tmp));
		bfs(car[i].first, car[i].second, i);
	}
	search();
	return 0;
}