[백준/BOJ] 백준 1348번 : 주차장

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

1348번: 주차장

차에서 주차장으로 연결되는 그래프를 만들고 이분 탐색을 통해 최소 거리를 구했다. 해당 거리 안에 모든 차가 주차 가능한지 확인하는 것은, vector<int> parked_car(251, 0); ([주차번호] = (주차된 차 번호)) 를 통해 주차된 차를 저장하고, 각각의 차를 확인할 때마다 vector<int> this_selected_car(251, 0); ([차번호] = (해당 차를 이번 선택에서 주차장을 골랐는지))를 이용하여 해당 차가 이번 선택에서 주차장을 골랐는지 확인하여 문제를 해결했다. 이런 방법을 이용하여 주차장에 들어간 차가 다른 주차장으로 옮겨질 수 있는 것과 같은 방법을 고려했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <queue>
using namespace std;

int r, c;
vector<string> board;
vector<vector<int>> car_check(50, vector<int>(50, 0));
vector<vector<int>> park_check(50, vector<int>(50, 0));
vector<vector<int>> car_park(251, vector<int>(251, -1)); //[차 번호][주차 번호] = 거리
vector<pair<int, int>> adj[251]; //[차 번호] , (거리,주차번호)
int car_cnt = 0;
int park_cnt = 0;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void Make_Graph()
{
	for (int i = 1; i <= car_cnt; i++)
		for (int j = 1; j <= park_cnt; j++)
		{
			if (car_park[i][j] != -1)
			{
				adj[i].push_back(make_pair(car_park[i][j], j));
			}
		}
}

//car차의 주차장 고르기
bool Select_park(int car, int dist, vector<int>& this_selected_car, vector<int>& parked_car)
{
	//이번 선택에서 주차장을 골랐던 차 일때
	if (this_selected_car[car] == 1)
		return false;

	//이번 선택에서 해당 차의 주차장을 고른다고 체크
	this_selected_car[car] = 1;

	for (int i = 0; i < adj[car].size(); i++)
	{
		int this_dist = adj[car][i].first;
		int this_park = adj[car][i].second;

		//갈 수 있는 거리의 주차장일때
		if (this_dist <= dist)
		{
			//해당 주차장에 들어간 차가 없을때
			if (parked_car[this_park] == 0)
			{
				parked_car[this_park] = car; //해당 주차장에 car차를 주차한다

				return true;
			}

			else
			{
				//해당 주차장에 들어간 차가 다른 주차장으로 옮겨질 수 있을때
				if (Select_park(parked_car[this_park], dist, this_selected_car, parked_car) == true)
				{
					parked_car[this_park] = car; //해당 주차장에 car차를 주차한다

					return true;
				}
			}
		}
	}

	return false;
}

//dist거리 안에 모든 차가 주차 가능한지 확인
bool Check(int dist)
{
	vector<int> parked_car(251, 0); //[주차번호] = (주차된 차 번호)

	//모든 차를 확인한다
	for (int i = 1; i <= car_cnt; i++)
	{
		vector<int> this_selected_car(251, 0); //[차번호] = (해당 차를 이번 선택에서 주차장을 골랐는지)

		if (Select_park(i, dist, this_selected_car, parked_car) == false)
			return false; //i번 차를 주차할 수 없을때
	}

	return true;
}

//해당 차에서 모든 주차칸까지 거리를 구한다
void Dist(int car_number, pair<int, int> car_start)
{
	vector<vector<int>> discovered(50, vector<int>(50, 0));
	vector<vector<int>> depth(50, vector<int>(50, 0));
	queue<pair<int, int>> q;
	int find_park = 0;

	discovered[car_start.first][car_start.second] = 1;
	depth[car_start.first][car_start.second] = 0;
	q.push(car_start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//주차장을 발견했을때
		if (park_check[here.first][here.second] != 0)
		{
			int park_number = park_check[here.first][here.second];
			car_park[car_number][park_number] = depth[here.first][here.second];

			find_park++;

			if (find_park == park_cnt)
				break;
		}

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && board[there.first][there.second] != 'X' && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;
				q.push(there);
			}
		}

	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (board[i][j] == 'C')
			{
				car_cnt++;
				car_check[i][j] = car_cnt;
			}

			else if (board[i][j] == 'P')
			{
				park_cnt++;
				park_check[i][j] = park_cnt;
			}
		}
	}

	if (car_cnt == 0)
	{
		cout << 0 << "\n";

		return 0;
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (car_check[i][j] != 0)
			{
				int car_number = car_check[i][j];
				Dist(car_number, make_pair(i, j));
			}
		}
	}

	Make_Graph();

	int left = 0;
	int right = 2500;
	int result = -1;

	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (Check(mid) == true)
		{
			result = mid;

			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	cout << result << "\n";

	return 0;
}