취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1348번 문제인 주차장이다.
문제는 아래 링크를 확인하자.

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

각 차들과 주차칸까지의 거리를 bfs를 이용해 구하고, 각 차와 각 주차장 사이에 에지를 연결해 이분그래프를 만들 수 있다. 이 과정에서 모든 차와 주차장들이 연결되어있지 않을 수 있다는 점에 유의하여 구현하자.

이제 각 차를 거리가 mid 이하만큼 떨어진 주차장에 모두 주차할 수 있는지 여부를 각각 이분매칭을 통해 구하고, 그 여부에 따라 차를 이동해야하는 거리를 구해내는 이진탐색을 진행하면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#define NODE 201
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

int N;
vector<pair<int,int>> G[NODE];
int visited[NODE];
int matching[NODE];

int bpfunc(int current, int mid) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto& node : G[current]) {
		if (node.second > mid) continue;
		if (matching[node.first] == 0) {
			matching[node.first] = current;
			return 1;
		}
		if (bpfunc(matching[node.first], mid)) {
			matching[node.first] = current;
			return 1;
		}
	}
	return 0;
}

int bipartitematching(int mid) {
	memset(matching, 0, sizeof(matching));
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		ret += bpfunc(i, mid);
	}

	return ret;
}

int R, C;
string board[50];
vector<pair<int, int>> parking;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
int dist[50][50];
queue<pair<int, int>> que;
void bfs(int r, int c) {
	memset(dist, 0, sizeof(dist));
	dist[r][c] = 1;
	que.push(make_pair(r, c));
	while (!que.empty()) {
		auto p = que.front(); que.pop();
		r = p.first, c = p.second;
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (dist[rr][cc] || board[rr][cc] == 'X') continue;
			dist[rr][cc] = dist[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'P') {
				parking.emplace_back(make_pair(r, c));
			}
		}
	}

	int pcnt = parking.size();
	int ccnt = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'C') {
				ccnt++;
				bfs(r, c);
				for (int p = 0; p < pcnt; p++) {
					int d = dist[parking[p].first][parking[p].second];
					if (d == 0) continue;
					G[ccnt].emplace_back(make_pair(p + 1, d));
				}
			}
		}
	}

	N = ccnt;
	int low = 0, high = 2500;
	while (low < high) {
		int mid = (low + high) / 2;
		if (bipartitematching(mid) == ccnt) high = mid;
		else low = mid + 1;
	}

	if (ccnt == 0) cout << 0;
	else if (low == 2500) cout << -1;
	else cout << low - 1;
}